如果一个数列至少有三个元素,并且任意两个相邻元素之差相同,则称该数列为等差数列。

数组 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. 连续等差数组的长度与等差数组的子数组个数的关系

三个数的时候,个数为1;四个的时候,个数为3;五个的时候,个数为6;可以观察到,没增加一个连续的等差数列,子数组个数就增加n-1个,其中n 是增加前的连续等差数个数

  1. 不连续的情况

从最后一个连续的数开始往后遍历,遇到连续三个等差数列的情况再进行分析遍历

  1. 数组长度小于三情况

直接返回0

编码实现

/**
 * @param {number[]} A
 * @return {number}
 */
var numberOfArithmeticSlices = function(A) {
    if (A.length < 3) { // 传入数组长度小于三,直接返回
        return 0
    }
    let sum = 0 // 总个数
    for (let i = 0; i < A.length-2; ++i) { // 遍历整个数组
        let d = A[i+1] - A[i] // 当前元素跟后一个元素的差
        let d1 = A[i+2] - A[i+1] // 后一个元素与后后一个元素的差
        let tmpsum = 0 // 这一轮遍历的等差数组的子数组的个数
        if (d1 === d) { // 两个差相等,构成最小的等差数列长
            i += 2
            tmpsum = 1
            let step = 2 // 等差数组的长度每增加一,子数组的个数增加 n-1; n 为当前等差数组的长度
            while (i < A.length-1 && A[i+1] - A[i] === d) {
                tmpsum += step
                step++
                ++i
            }
            --i // 下一次遍历从当前等差数组的最后一个元素开始
        }
        sum += tmpsum
    }
    return sum // 返回总数
};