如果一个数列至少有三个元素,并且任意两个相邻元素之差相同,则称该数列为等差数列。
数组 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;四个的时候,个数为3;五个的时候,个数为6;可以观察到,没增加一个连续的等差数列,子数组个数就增加n-1
个,其中n
是增加前的连续等差数个数
- 不连续的情况
从最后一个连续的数开始往后遍历,遇到连续三个等差数列的情况再进行分析遍历
- 数组长度小于三情况
直接返回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 // 返回总数
};