题目描述
如果一个数列至少有三个元素,并且任意两个相邻元素之差相同,则称该数列为等差数列。
例如,以下数列为等差数列:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
以下数列不是等差数列。
1, 1, 2, 5, 7
数组 A
包含 N
个数,且索引从 0 开始。数组 A
的一个子数组划分为数组 (P, Q)
,P
与 Q
是整数且满足 0 <= P < Q < N
。
如果满足以下条件,则称子数组 (P, Q)
为等差数组:
元素 A[P], A[P + 1], ..., A[Q - 1], A[Q]
是等差的。并且 P + 1 < Q
。
函数要返回数组 A
中所有为等差数组的子数组个数。
样例
A = [1, 2, 3, 4]
返回:3
A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。
算法
(差分数组) $O(n)$
- 首先将原数组进行差分,即对于
0 <= i < n - 1
,diff[i] = A[i + 1] - A[i]
。 - 我们找每个连续相同的差值,如果这个连续相同差值的区间长度为
len
,则这段区间所产生的等差数组的个数为 $len * (len - 1) / 2$。
时间复杂度
- 遍历数组两次,故时间复杂度为 $O(n)$。
空间复杂度
- 需要额外的空间存储差分数组。
- 故空间复杂度也为 $O(n)$。
C++ 代码
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
int n = A.size();
if (n == 0)
return 0;
vector<int> diff(n - 1);
for (int i = 0; i < n - 1; i++)
diff[i] = A[i + 1] - A[i];
int last = 0, ans = 0;
for (int i = 1; i < n - 1; i++)
if (diff[i] != diff[i - 1]) {
ans += (i - last) * (i - last - 1) / 2;
last = i;
}
ans += (n - last - 1) * (n - last - 2) / 2;
return ans;
}
};
如果按Y总的写法,用原来的数组存差分数组,是不是空间=O(1)?
没毛病~
“则这段区间所产生的等差数组的个数为$(len−1)(len−2)/2$。” 应该是$C_{\text{len}}^2 = len(len - 1)/2$吧?
已修正