题目描述

数组 A 包含 N 个数，且索引从0开始。数组 A 的一个子数组划分为数组 (P, Q)，P 与 Q 是整数且满足 0<=P<Q<N 。

如果满足以下条件，则称子数组(P, Q)为等差数组：

元素 A[P], A[p + 1], …, A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q 。

函数要返回数组 A 中所有为等差数组的子数组个数。

样例

A = [1, 2, 3, 4]

返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。

算法1

(差分数组) $O(n)$

1.什么是差分数组？
一个数组为[a1, a2, a3, a4]，其差分数组为[b1, b2, b3, b4]，即[a1, a2-a1, a3-a2, a4-a3]

2.解法：这题本质上就是求出差分数组中连续相等区间，再找出每个区间内长度大于3的子区间个数，最后求和
假设一段区间内有k个数，1,2,3,...k(下标)
左端点取1时，右端点可取2,3,...k，共k-1个
左端点取2时，右端点可取3,4,...k，共k-2个
...
左端点取k-1时，又端点可取k，共1个
所以子区间个数为k(k-1)/2

你可能会问，为什么左端点取1的时候，右端点不是取3呢，不是至少3个数才能成为等差数列吗
因为b2=a2-a1, b3=a3-a2，其中已经包含3个数了

Java 代码

class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        for(int i = A.length-1; i > 0; i--) A[i] -= A[i-1];
        int res = 0;
        for(int i = 1; i < A.length; ){
            int j = 1;
            while(i + 1 < A.length && A[i+1] == A[i]){
                i++;
                j++;
            }
            res += j * (j - 1) / 2; 
            i++;
        }
        return res;
    }
}