LeetCode Arithmetic Slices
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, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
The following sequence is not arithmetic.
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.
Example:
A = [1, 2, 3, 4]
return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.
本题要求一个数组中等差数列的个数，并不要求是最长的等差数列。比如给的例子中数组A=[1,2,3,4]，可以抽出3个等差数列，分别是[1,2,3]、[2,3,4]、[1,2,3,4]。
首先还是找特征，我们可以在数组中先找出最长的等差数列，然后在等差数列的基础上抽取（Slice）出比较小的等差数列，所以先研究一下长度为n的等差数列可以抽出多少个小的等差数列。
- n=3，抽出1个
- n=4，抽出3=1+2个，即1个长度为4的和2个长度为3的
- n=5，抽出6=1+2+3个，即1个长度为5的、2个长度为4的和3个长度为3的
- n=6，抽出10=1+2+3+4个，即…
- …
由此可以得出规律，长度为n的等差数列，可以抽出1+2+…+(n-2)=(n-1)(n-2)/2个小的等差数列。
于是问题就转换为找出数组中所有最长连续等差数列，然后代入上述公式计算。
完整代码如下：
[cpp]
class Solution {
public:
inline int slice(int cnt) {
if (cnt < 3)return 0;
if (cnt == 3)return 1;
return (cnt – 1)*(cnt – 2) / 2; // 1+2+…+(cnt-2)
}
int numberOfArithmeticSlices(vector<int>& A) {
if (A.size() < 3)return 0;
int ans = 0, cnt = 2, diff = A[1] – A[0];
for (int i = 2; i < A.size(); ++i) {
if (A[i] – A[i – 1] == diff) {
++cnt;
}
else {
ans += slice(cnt);
cnt = 2;
diff = A[i] – A[i – 1];
}
}
return ans + slice(cnt);
}
};
[/cpp]
本代码提交AC，用时3MS。
网上还有一种
DP解法，我们看看上面的规律，当n从4增加到5时，抽取出来的小等差数列增加了3个，是在n=4时，最后+2的基础上+1=3；当n从5增加到6时，抽取出来的小等差数列增加了4个，是在n=5时，最后+3的基础上+1=4。
所以我们设置一个dp数组，dp[i]表示：如果第i个元素和前面构成等差数列了，则能贡献多少个小等差数列，根据前面的分析，dp[i]=dp[i-1]+1，这里的dp相当于比如n=6时的10=1+2+3+4（等号右边的数组）；如果第i个元素不和前面构成等差数列，则dp[i]=0不贡献小等差数列。
这种解法的代码如下：
[cpp]
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
if (A.size() < 3)return 0;
int ans = 0;
vector<int> dp(A.size(), 0);
for (int i = 2; i < A.size(); ++i) {
if (A[i] – A[i – 1] == A[i – 1] – A[i – 2]) {
dp[i] = dp[i – 1] + 1;
}
ans += dp[i];
}
return ans;
}
};
[/cpp]
本代码提交AC，用时3MS。
DP一般都可以优化空间，上面的解法也可以不用一个dp数组，而只用一个变量。如下：
[cpp]
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
if (A.size() < 3)return 0;
int ans = 0, cur = 0;
for (int i = 2; i < A.size(); ++i) {
if (A[i] – A[i – 1] == A[i – 1] – A[i – 2]) {
++cur;
}
else {
cur = 0;
}
ans += cur;
}
return ans;
}
};
[/cpp]
本代码提交AC，用时也是3MS。]]>