413. Arithmetic Slices.md

413. Arithmetic Slices

思路

题目要求一个数组中存在多少个构成等差数列的子数组。注意子数组是数组中的一个连续序列。由于要求连续，我们可以先考虑一个长度为 n 的等差数列，有多少个子数组呢？很显然长度为3的有n-2个、长度为4的有n-3个、......长度为n的有1个，故一共有 1 + 2 + ... + (n-2) = (n-1)(n-2)/2 个。

所以我们可以从前往后遍历数组nums，找到长度尽可能长的上述等差数列，这样就可以计算出这个等差数列有多少子数组了。

由于只用遍历一遍，故复杂度为O(n)。

C++

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        if(nums.size() < 3) return 0;
        int res = 0;
        // d为当前等差数列的差, cnt为当前等差数列的长度
        int d = nums[1] - nums[0], cnt = 2;
        for(int i = 2; i < nums.size(); i++){
            if(nums[i] == nums[i-1] + d){
                cnt += 1;
            }else{ // 差发生变化, 计算结果
                if(cnt >= 3) res += (cnt - 2) * (cnt - 1) / 2;
                d = nums[i] - nums[i-1]; // 更新差和长度
                cnt = 2;
            }
        }
        if(cnt >= 3) res += (cnt - 2) * (cnt - 1) / 2;
        return res;
    }
};