LeetCode 413. 等差數(shù)列劃分
如果一個(gè)數(shù)列至少有三個(gè)元素，并且任意兩個(gè)相鄰元素之差相同，則稱該數(shù)列為等差數(shù)列。
例如，以下數(shù)列為等差數(shù)列:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
以下數(shù)列不是等差數(shù)列淘捡。
1, 1, 2, 5, 7
數(shù)組 A 包含 N 個(gè)數(shù)，且索引從0開(kāi)始池摧。數(shù)組 A 的一個(gè)子數(shù)組劃分為數(shù)組 (P, Q)焦除，P 與 Q 是整數(shù)且滿足 0<=P<Q<N 。
如果滿足以下條件作彤，則稱子數(shù)組(P, Q)為等差數(shù)組：
元素 A[P], A[p + 1], ..., A[Q - 1], A[Q] 是等差的膘魄。并且 P + 1 < Q 。
函數(shù)要返回?cái)?shù)組 A 中所有為等差數(shù)組的子數(shù)組個(gè)數(shù)竭讳。
示例:
A = [1, 2, 3, 4]
返回: 3, A 中有三個(gè)子等差數(shù)組: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]创葡。
我的答案：
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
vector<long> seqLen;
long len = 0;
int ans = 0;
if(A.size() < 3) return 0;
for(int i=0; i<A.size()-2; i++){
len = 0;
while(A[i+1]-A[i] == A[i+2] - A[i+1]){
len++;
i++;
if(i == A.size()-2) break;
}
//這里不能有i++！若有绢慢，則檢測(cè)：
//[2]-[1] == [4]-[3]; [8]-[7] == [6]-[5];
//未檢測(cè)[6]-[5] == [4]-[3];
seqLen.push_back(len + 2);
}
for(int i=0; i<seqLen.size(); i++){
if(seqLen[i] > 2){
for(int j = seqLen[i]; j>2; j--){
ans = ans + seqLen[i] - j + 1;
}
}
}
return ans;
}
};
