对长度为len的等差数组递推出计算表达式:(n-1)*(n-2)/2, n为数组长度
然后遍历找到各个n即可
使用差分数组,代码会更加简洁些
可以参考 ref
C++ 代码
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
int res = 0;
int n = nums.size();
const int INF = 1e5;
int cnt = 0;
for(int i=1, diff = INF; i<n; ++i) {
if(diff == INF){
diff = nums[i] - nums[i-1];
cnt = 2;
} else {
int t = nums[i] - nums[i-1];
if(t == diff) cnt++;
else {
res += (cnt-1) * (cnt-2) / 2;
diff = INF;
i--;
}
}
}
if(cnt>=3)res += (cnt-1) * (cnt-2) / 2;
return res;
}
};