LeetCode413 Arithmetic Slices

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequence:

1
2
3
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

The following sequence is not arithmetic.

1
1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.

A slice (P, Q) of array A is called arithmetic if the sequence:
A[P], A[p + 1], …, A[Q - 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.

The function should return the number of arithmetic slices in the array A.

样例

1
2
3
4
5
6
7
Input:
A = [1, 2, 3, 4]
Output:
3

for 3 arithmetic slices in A:
[1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

思路

给一个序列,找出其中有多少个连续的子序列是等差序列。


一个直观的想法是,双指针扫一遍数组,每次确定一个最长的等差序列$a[l..r]$,那么这个等差序列对答案的贡献是 $(len - 2) * (len - 1) / 2$,其中$len = r - l + 1$。


另一个做法是使用动态规划,设$dp[i]$表示以$a[i]$结尾的等差序列的个数。

如果$a[i] - a[i-1] == a[i-1] - a[i-2]$,那么有$dp[i] = dp[i-1] + 1$,否则$dp[i] = 0$。

其中$dp[i] = dp[i-1] + 1$是怎么来的呢?

根据条件$a[i] - a[i-1] == a[i-1] - a[i-2]$我们知道,所有以$a[i-1]$结尾的等差序列,现在加上$a[i]$之后依然是等差序列。同时,还新增一个只有3个元素的等差序列$a[i-2 .. i]$,所以$dp[i] = dp[i-1] + 1$。

最后,答案$ans = \sum^{n-1}_{i=0} {dp[i]}$

代码

双指针:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
int ans = 0, n = A.size();
if (n < 3) return 0; // 小于3个元素,答案为0
int diff = A[1] - A[0]; // 当前序列的公差
int l = 0, r = 2, len;
while (l < n && r < n) {
// 更新等差序列的右端点r
while (r < n && A[r] - A[r - 1] == diff) r++;
len = r - l; // 当前等差序列为a[l..r-1]
// 计算该序列贡献的答案
if (len >= 3) ans += (len - 2) * (len - 1) / 2;
l = r - 1; r++; // 更新左右端点
if (l + 1 < n) diff = A[l + 1] - A[l]; // 更新公差
}
return ans;
}
};

DP:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
int ans = 0, n = A.size();
if (n < 3) return 0;
vector<int> dp(n, 0); // 初始化
dp[2] = (A[2] - A[1] == A[1] - A[0]);
ans += dp[2];
for (int i = 3; i < n; ++i) {
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
dp[i] = dp[i - 1] + 1;
}
ans += dp[i];
}
return ans;
}
};

分享到 评论