leetcode 413. Arithmetic Slices

413. Arithmetic Slices

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        int count = 0;
        int sum = 0;
        
        for(int i = 2; i < A.size(); i++){
            if(A[i] + A[i - 2] == (A[i - 1] << 1)) count++;
            else{
                sum += count * (count + 1) >> 1;
                count = 0;
            }        
        }
        sum += count * (count + 1) >> 1;
        return sum;
    }
};

分析

做了这道题发现做题还是要抓住题眼子。像割绳子，背包问题，像是一个连续的模型，因为每个部分都可能是最优解的一部分。

而这道题，更像是一个离散的模型，因为说，不是数组的每个元素都对最优解的构造有贡献，只有那些可以构成arithmetic slices的元素，才对最优解的构造有贡献。

这个数列就像一个海洋，其中有若干个arithmetic slices的孤岛。于是sum就是这若干个孤岛中arithmetic slices的总和。

于是核心问题就成了如何计算孤岛中arithmetic slices的个数，若孤岛大小为3，则个数为1；若孤岛大小为4，则个数为3；若孤岛大小为5，则个数为6…可以发现，只要知道孤岛的大小，孤岛中arithmetic slices个数的问题就可以解决了。