题目
如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。
- 例如，
[1,3,5,7,9]、[7,7,7,7]和[3,-1,-5,-9]都是等差数列。
给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。
子数组 是数组中的一个连续序列。
示例 1：
输入：nums = [1,2,3,4]
输出：3
解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。
示例 2：
输入：nums = [1]
输出：0
提示：
1 <= nums.length <= 5000-1000 <= nums[i] <= 1000
思路与代码
方法一：双指针法
有几个关键点我们必须要清晰，等差数列，子数组。
- 等差数列是指从第二项起，每一项与它的前一项的差等于同一个常数的一种数列
- 子数组是数组中的一个连续序列，连续，长度至少为3
- 一个子数组如果分为前后两部分，前面不是等差数列，那么后面部分就不用判断了
因此，对于每个起始位置，我们只需要向后进行一遍扫描，不断累加，直到不再构成等差数列为止，此时，已经没有必要再向后扫描了。
代码
int numberOfArithmeticSlices(vector<int>& nums) {
int len = nums.size();
int res = 0;
for (int i = 0; i < len - 2; i++) {
int d = nums[i + 1] - nums[i];
for (int j = i + 1; j < len - 1; j++) {
if (nums[j + 1] - nums[j] == d)
res++;
else
break;
}
}
return res;
}
时间复杂度：$O(N^{2})$
空间复杂度：$O(1)$
方法二：双指针法优化
很明显，上面的双指针法，我们已经知道，以4为开头的[4,6,8,10]是等差子数组，再计算以6为开头的[6,8,10]是否为等差数组，重复计算。那我们如何知道长度为L的等差数列对结果的贡献呢?
我们不妨枚举一下。
- 长度为 3 的连续的等差数列，有 4 个
- 长度为 4 的连续的等差数列，有 3 个
- 长度为 5 的连续的等差数列，有 2 个
- 长度为 6 的连续的等差数列，有 1 个
所以，长度为L的等差数列对结果的贡献为，
$$
(L-2)+(L-3)+…+2+1=\frac{\left(L-2+1\right)\left(L-2\right)}{2}=\frac{\left(L-1\right)\left(L-2\right)}{2}
$$
代码
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
int len = nums.size();
if (len < 3) {
return 0;
}
// 初始化
int preDiff = nums[1] - nums[0];
// 当前得到的等差数列的长度，有「差」必有两个元素，因此初始化的时候 L = 2
int L = 2;
int res = 0;
// 从下标 2 开始比较「当前的差」与「上一轮的差」是否相等
for (int i = 2; i < len; i++) {
int diff = nums[i] - nums[i - 1];
if (diff == preDiff) {
L++;
}
else {
// 加入结果，然后重置 L 和 preDiff
res += (L - 1) * (L - 2) / 2;
L = 2;
preDiff = diff;
}
}
// 最后还要再计算一下结果
res += (L - 1) * (L - 2) / 2;
return res;
}
};
这个答案得出来的分数有点低，主要在于我们每一步都计算一次等差数列。其实，我们可以用一个while循环来跳到不相等的位置再计算子数组对结果的贡献。
补充1
长度为L的连续子序列中，长度为3的连续等差数列的个数为L-2，可以从下面这张图看出来。
- 长度为 3 的连续的等差数列，结尾留2个位置，对结果的贡献为，
L-2 - 长度为 4 的连续的等差数列，结尾留3个位置，对结果的贡献为，
L-3 - 长度为 5 的连续的等差数列，结尾留4个位置，对结果的贡献为，
L-4 - 长度为 6 的连续的等差数列，结尾留5个位置，对结果的贡献为，
L-5
补充2
等差数列的基本公式为，和(S) = (首项 + 末项) x 项数 ÷ 2。项数(n) = (末项 - 首项) ÷公差+1