Hard

题目描述

给你一个整数数组 nums ，返回 nums 中所有等差子序列的数目。

如果一个序列中 至少有三个元素 ，并且任意两个相邻元素之间的差都相同，那么这个序列就是等差序列。

  • 例如，[1, 3, 5, 7, 9]、[7, 7, 7, 7] 和 [3, -1, -5, -9] 都是等差序列。
  • 相反，[1, 1, 2, 5, 7] 不是等差序列。

数组的子序列是从数组中删除一些元素（也可能不删除）得到的一个序列。

  • 例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。

题目数据保证答案是一个 32-bit 整数。

示例 1：

输入：nums = [2,4,6,8,10]
输出：7
解释：所有的等差子序列为：
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

示例 2：

输入：nums = [7,7,7,7,7]
输出：16
解释：数组中的任意子序列都是等差子序列。

提示：

  • 1 <= nums.length <= 1000
  • -2^31 <= nums[i] <= 2^31 - 1

解题思路

解题思路

这是一道关于等差数列的动态规划题，关键是要理解子序列的特性以及如何统计所有可能的等差子序列。

核心思路

我们可以使用动态规划来解决这个问题。定义 dp[i][d] 表示以位置 i 结尾、公差为 d 的等差子序列数量（包括长度为 2 的序列）。

状态转移

对于每个位置 i，我们需要考虑之前所有位置 j (j < i)：

  • 计算公差 d = nums[i] - nums[j]
  • 如果存在以 j 结尾、公差为 d 的序列，那么可以将 nums[i] 添加到这些序列后面
  • dp[i][d] += dp[j][d] + 1（+1 表示新形成的长度为 2 的序列 [nums[j], nums[i]]）

结果统计

由于题目要求至少 3 个元素的等差序列，所以我们只统计 dp[j][d] 的贡献（不包括新形成的长度为 2 的序列）。

注意事项

  • 使用 unordered_map 存储不同公差对应的序列数量
  • 公差可能很大，需要使用 long long 类型避免溢出
  • 每次转移时，先累加到结果中，再更新 dp 值

代码实现

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        if (n < 3) return 0;
        
        vector<unordered_map<long long, int>> dp(n);
        int result = 0;
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                long long diff = (long long)nums[i] - nums[j];
                
                if (dp[j].count(diff)) {
                    result += dp[j][diff];
                    dp[i][diff] += dp[j][diff] + 1;
                } else {
                    dp[i][diff] = 1;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 3:
            return 0
        
        dp = [defaultdict(int) for _ in range(n)]
        result = 0
        
        for i in range(1, n):
            for j in range(i):
                diff = nums[i] - nums[j]
                
                if diff in dp[j]:
                    result += dp[j][diff]
                    dp[i][diff] += dp[j][diff] + 1
                else:
                    dp[i][diff] = 1
        
        return result

public class Solution {
    public int NumberOfArithmeticSlices(int[] nums) {
        int n = nums.Length;
        if (n < 3) return 0;
        
        var dp = new Dictionary<long, int>[n];
        for (int i = 0; i < n; i++) {
            dp[i] = new Dictionary<long, int>();
        }
        
        int result = 0;
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                long diff = (long)nums[i] - nums[j];
                
                if (dp[j].ContainsKey(diff)) {
                    result += dp[j][diff];
                    dp[i][diff] = dp[i].GetValueOrDefault(diff, 0) + dp[j][diff] + 1;
                } else {
                    dp[i][diff] = 1;
                }
            }
        }
        
        return result;
    }
}

var numberOfArithmeticSlices = function(nums) {
    const n = nums.length;
    if (n < 3) return 0;
    
    const dp = new Array(n).fill(null).map(() => new Map());
    let result = 0;
    
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            const diff = nums[i] - nums[j];
            
            if (dp[j].has(diff)) {
                result += dp[j].get(diff);
                dp[i].set(diff, (dp[i].get(diff) || 0) + dp[j].get(diff) + 1);
            } else {
                dp[i].set(diff, 1);
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)双重循环遍历所有位置对
空间复杂度O(n²)最坏情况下每个位置存储 O(n) 个不同公差

相关题目