LeetCode 413. Arithmetic Slices

题目：
A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequence:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

The following sequence is not arithmetic.

1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.

A slice (P, Q) of array A is called arithmetic if the sequence:
A[P], A[p + 1], …, A[Q - 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.

The function should return the number of arithmetic slices in the array A.

Example:

A = [1, 2, 3, 4]
return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

思路1： 就是求所有满足arithmetic的子串的个数 ，包括本身。重点在else部分的求结果，具体思路见注释~。

代码1：

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        int res = 0;
        int count = 0;//记录当前有几个连续3个数满足arithmetic
        int sub1;//当前位和前一位的差
        int sub2;//当前位和后一位的差
        int len = A.size();
        if (len < 3){//长度小于3，直接返回0
            return 0;
        }
        for (int i = 1; i < len - 1; ++i){
            sub1 = A[i] - A[i - 1];
            sub2 = A[i + 1] - A[i];
            if (sub2 == sub1){//两个差相等，则++count
                ++count;
            }
            else{//如果不是，如果当前有count个连续3个整数满足arithmetic，比如{1，2，3，4，6}此时count为2
                res += count*(count + 1) / 2;//结果加上这个，count置0
                count = 0;
            }
        }
        if (count){//如果有那种结果还满足的，比如{1，2，3，4}，就不执行else部分，所以要进行一次res计算
            res += count*(count + 1) / 2;
        }
        return res;
    }
};

结果： 3ms

思路2： 利用动态规则的思想 dp[i]=dp[i-1]+1，具体思路见注释

代码2：

int numberOfArithmeticSlices(vector<int>& A) {
    int n = A.size();
    if (n < 3) return 0;
    vector<int> dp(n, 0); //以A[i]结尾的arithmetic的数量 
    if (A[2] - A[1] == A[1] - A[0]) dp[2] = 1; //判断前三个数是不是满足arithmetic
    int result = dp[2];
    for (int i = 3; i < n; ++i) {
        if (A[i] - A[i - 1] == A[i - 1] - A[i - 2])//如果当前三个数满足arithmetic
            dp[i] = dp[i - 1] + 1;//当前的dp[i]为前一个加1
        result += dp[i]; //更新结果
    }
    return result;
}