题目

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]

分析

给定一串数字，输出有多少个至少有三个数的等差数列。
这里是使用的动态规划增量思想，比如1,2,3,4,5,7序列，扫描到3的时候增加了1个有效数列1,2,3，到4的时候增加了2个【2,3,4】和【1,2,3,4】,到5的时候增加了3个【3,4,5】【2,3,4,5】和【1,2,3,4,5】，把每次增加的数量累加起来就是最终结果

代码

public int numberOfArithmeticSlices(int[] A) {
    if(A.length < 3) return 0;
    int n = A.length;
    int cur = 0, total = 0;  //cur表示增量，total为总量
    for(int i = 2; i < n; ++i){
        if(A[i] - A[i-1] == A[i-1] - A[i-2]){
            cur ++;
            total += cur;
        }else{
            cur = 0;
        }
    }
    return total;
}