问题描述 链接到标题

413.等差数列划分

解题思路 链接到标题

注意到子数组个数$cnt = len - 3 + 1 + len - 4 + 1 + … + 1$，其中len是等差数组的长度，则cnt = (n - 1) * (n - 2) / 2，每次遍历找出连续的等差数组的长度即可。 测试test

代码 链接到标题 

class Solution {
  public:
    int numberOfArithmeticSlices(vector<int> &nums) {
        if (nums.size() < 3)
            return 0;
        int dif = nums[1] - nums[0];
        int len = 2;
        int cnt = 0;
        for (int i = 2; i < nums.size(); i++) {
            if (nums[i] - nums[i - 1] == dif)
                len++;
            else {
                if (len >= 3)
                    cnt += (len - 2) * (len - 1) / 2;
                len = 2;
                dif = nums[i] - nums[i - 1];
            }
        }
        if (len >= 3)
            cnt += (len - 2) * (len - 1) / 2;
        return cnt;
    }
};