描述
寻找等差数列的个数
样例1
2输入: [1,2,3,4]
输出: 3 有[1,2,3],[2,3,4]以及[1,2,3,4]
我的解法
注意到每次多加一个数字后,增加的等差数列个数与当前等差数列的长度有关。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
if (A.size() < 3) { return 0; }
int gap = A[1]-A[0];
int len = 2;
int sum = 0;
for (int i = 2; i < A.size(); i++) {
int tempgap = A[i] - A[i-1] ;
if (tempgap == gap) {
len++;
sum += len - 2;
}
else {
len = 2;
gap = tempgap;
}
}
return sum;
}
};
其他解法
关键在于对每增加一个长度后对等差数列个数的影响。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution {
public:
int sum1toN(int n) {
return n * (n + 1) / 2;
}
int numberOfArithmeticSlices(vector<int>& A) {
if (A.size() < 3) { return 0; }
int gap = A[1] - A[0];
int len = 0;
int sum = 0;
for (int i = 2; i < A.size(); i++) {
int tempgap = A[i] - A[i - 1];
if (tempgap == gap) {
len++;
}
else {
sum += sum1toN(len);
len = 0;
gap = tempgap;
}
}
return len=0?sum:sum+sum1toN(len);
}
};
参考资料
原题链接