Medium

题目描述

如果一个整数数组至少包含三个元素，并且任意两个相邻元素之间的差都相同，那么这个数组就被称为等差数组。

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

解题思路

解题思路

这道题要求找出数组中所有等差子数组的个数。我们可以通过动态规划来解决。

核心思想： 如果我们知道了以位置 i 结尾的最长等差子数组的长度，就能计算出以该位置结尾的所有等差子数组个数。

分析过程：

  1. 对于长度为 n 的等差数组，其包含的等差子数组个数为 (n-2) + (n-3) + ... + 1 = (n-1)*(n-2)/2
  2. 更简单的思考方式：如果当前位置能延续前面的等差数列，那么新增的等差子数组个数等于当前等差数列的长度减2

算法步骤：

  1. 用 dp[i] 表示以位置 i 结尾的等差子数组个数
  2. 如果 nums[i] - nums[i-1] == nums[i-1] - nums[i-2]，说明可以延续等差数列
  3. 此时 dp[i] = dp[i-1] + 1，因为在原有基础上，加上当前元素又形成了一个新的等差子数组
  4. 累加所有 dp[i] 就是答案

这种方法时间复杂度为 O(n)，空间复杂度可以优化到 O(1)。

代码实现

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        if (n < 3) return 0;
        
        int result = 0;
        int dp = 0;  // 以当前位置结尾的等差子数组个数
        
        for (int i = 2; i < n; i++) {
            if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) {
                dp = dp + 1;
                result += dp;
            } else {
                dp = 0;
            }
        }
        
        return result;
    }
};

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 3:
            return 0
        
        result = 0
        dp = 0  # 以当前位置结尾的等差子数组个数
        
        for i in range(2, n):
            if nums[i] - nums[i-1] == nums[i-1] - nums[i-2]:
                dp += 1
                result += dp
            else:
                dp = 0
        
        return result

public class Solution {
    public int NumberOfArithmeticSlices(int[] nums) {
        int n = nums.Length;
        if (n < 3) return 0;
        
        int result = 0;
        int dp = 0;  // 以当前位置结尾的等差子数组个数
        
        for (int i = 2; i < n; i++) {
            if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) {
                dp = dp + 1;
                result += dp;
            } else {
                dp = 0;
            }
        }
        
        return result;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var numberOfArithmeticSlices = function(nums) {
    const n = nums.length;
    if (n < 3) return 0;
    
    let result = 0;
    let dp = 0;  // 以当前位置结尾的等差子数组个数
    
    for (let i = 2; i < n; i++) {
        if (nums[i] - nums[i-1]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)只需要遍历数组一次
空间复杂度O(1)只使用常数个额外变量

相关题目