413. 等差数列划分

题目描述

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

例如，[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

解法

方法一：遍历计数

我们用 \(d\) 表示当前相邻两个元素的差值，用 \(cnt\) 表示当前等差数列的长度，初始时 \(d = 3000\), \(cnt = 2\)。

遍历数组 nums，对于相邻的两个元素 \(a\) 和 \(b\)，如果 \(b - a = d\)，则说明当前元素 \(b\) 也属于当前等差数列，此时 \(cnt\) 自增 1；否则说明当前元素 \(b\) 不属于当前等差数列，此时更新 \(d = b - a\)，且 \(cnt = 2\)。如果 \(cnt \ge 3\)，则说明当前等差数列的长度至少为 3，此时等差数列的个数为 \(cnt - 2\)，将其加到答案中。

遍历结束后，即可得到答案。

在代码实现上，我们也可以将 \(cnt\) 初始化为 \(0\)，重置 \(cnt\) 时，直接将 \(cnt\) 置为 \(0\)；累加答案时，直接累加 \(cnt\) 即可。

时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。其中 \(n\) 是数组 nums 的长度。

相似题目：

Python3JavaC++GoTypeScript

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        ans = cnt = 0
        d = 3000
        for a, b in pairwise(nums):
            if b - a == d:
                cnt += 1
            else:
                d = b - a
                cnt = 0
            ans += cnt
        return ans

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int ans = 0, cnt = 0;
        int d = 3000;
        for (int i = 0; i < nums.length - 1; ++i) {
            if (nums[i + 1] - nums[i] == d) {
                ++cnt;
            } else {
                d = nums[i + 1] - nums[i];
                cnt = 0;
            }
            ans += cnt;
        }
        return ans;
    }
}

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int ans = 0, cnt = 0;
        int d = 3000;
        for (int i = 0; i < nums.size() - 1; ++i) {
            if (nums[i + 1] - nums[i] == d) {
                ++cnt;
            } else {
                d = nums[i + 1] - nums[i];
                cnt = 0;
            }
            ans += cnt;
        }
        return ans;
    }
};

func numberOfArithmeticSlices(nums []int) (ans int) {
    cnt, d := 0, 3000
    for i, b := range nums[1:] {
        a := nums[i]
        if b-a == d {
            cnt++
        } else {
            d = b - a
            cnt = 0
        }
        ans += cnt
    }
    return
}

function numberOfArithmeticSlices(nums: number[]): number {
    let ans = 0;
    let cnt = 0;
    let d = 3000;
    for (let i = 0; i < nums.length - 1; ++i) {
        const a = nums[i];
        const b = nums[i + 1];
        if (b - a == d) {
            ++cnt;
        } else {
            d = b - a;
            cnt = 0;
        }
        ans += cnt;
    }
    return ans;
}

413. 等差数列划分

题目描述

解法

方法一：遍历计数

评论