1.题目

如果一个数列至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。
例如，[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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/arithmetic-slices

2.思路

（1）查找最大长度的等差数列
① 长度为 3 等差数列，例如 [1, 2, 3]，其中只有一个长度为 3 的等差数列，即其自身 [1, 2, 3]

② 长度为 4 等差数列，例如 [1, 2, 3, 4]，其中：
长度为 4 的等差数列一共有 1 个，即 [1, 2, 3, 4]
长度为 3 的等差数列一共有 2 个，即 [1, 2, 3]、[2, 3, 4]
所以一共有 1 + 2 = 3 个等差数列。

② 长度为 5 等差数列，例如 [1, 2, 3, 4, 5]，其中：
长度为 5 的等差数列一共有 1 个，即 [1, 2, 3, 4, 5]
长度为 4 的等差数列一共有 2 个，即 [1, 2, 3, 4]、[2, 3, 4, 5]
长度为 3 的等差数列一共有 3 个，即 [1, 2, 3]、[2, 3, 4]、[3, 4, 5]
所以一共有 1 + 2 + 3 = 6 个等差数列。
…
以此类推，我们可以发现长度为 k 的等差数列，那么其任意长度大于等于 3 的连续子数列也必为等差数列，包含其自身和子数列一共有 (1 + 2 + 3 + … + k - 2) = (1 + k - 2) * (k - 2) / 2 = (k - 1) * (k - 2) / 2 个等差数列。

初始时 left = 0，所以我们只需在数组 nums 中查找以 nums[left] 为左端点的等差数列的最大长度（即要找出其右端点 nums[right]），那么便可以直接求出长度为 k = right - left + 1 的等差数列所包含的等差数列的总数，并用 res 进行累加保存。在此过程中，通过 left = right 来更新左端点，以达到不重复计数的目的。当 left = nums.length - 2 时，遍历结束，此时 res 即为数组 nums 中所有为等差数组的子数组个数。

（2）差分 & 计数
思路参考本题官方题解。

3.代码实现（Java）

//思路1————查找最大长度的等差数列
class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int res = 0;
        int length = nums.length;
        if (length < 3) {
            return res;
        }
        for (int left = 0, right = 0; left < length - 2;) {
            int diff = nums[left] - nums[left + 1];
            //查找以 nums[left] 为左端点的最大长度的等差数列的右端点 nums[right]
            while (right < length - 1 && nums[right] - nums[right + 1] == diff) {
                right++;
            }
            /*
                找到了长度为 k = right - left + 1 的等差数列，那么其任意长度大于等于 3 的连续子数列也必为等差数列，包含其自身和子数列一共
                有 (1 + 2 + 3 + ... + k - 2) = (1 + k - 2) * (k - 2) / 2 = (right - left) * (right - left - 1) / 2 个等差数列。
                例如 k = 5，等差数列为 [2,3,4,5,6]，那么
                长度为 5 的等差数列一共有 1 个，即 [2,3,4,5,6]
                长度为 4 的等差数列一共有 2 个，即 [2,3,4,5]、[3,4,5,6]
                长度为 3 的等差数列一共有 3 个，即 [2,3,4]、[3,4,5]、[4,5,6]
            */
            res += (right - left) * (right - left - 1) / 2;
            //更新左端点下标
            left = right;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

//思路2————差分 & 计数
class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int res = 0;
        int length = nums.length;
        if (length < 3) {
            return res;
        }
        int diff = nums[0] - nums[1];
        int tmpRes = 0;
        for (int i = 2; i < length; i++) {
            int curDiff = nums[i - 1] - nums[i];
            if (curDiff == diff) {
                tmpRes++;
            } else {
                diff = curDiff;
                tmpRes = 0;
            }
            res += tmpRes;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23