---

0446. 等差数列划分 II - 子序列

• 标签：数组、动态规划
• 难度：困难

题目链接

• 0446. 等差数列划分 II - 子序列 - 力扣

题目大意

描述：

给定一个整数数组 $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 \le nums.length \le 10^{3}$。
• $-2^{31} \le nums[i] \le 2^{31} - 1$。

示例：

• 示例 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：动态规划

1. 我们需要统计所有长度至少为 $3$ 的等差子序列的数目。
2. 使用动态规划，定义 $dp[i][d]$ 表示以位置 $i$ 结尾，公差为 $d$ 的等差子序列的数目。
3. 对于每个位置 $i$，我们遍历所有前面的位置 $j$（$j < i$），计算公差 $d = nums[i] - nums[j]$。
4. 如果 $dp[j][d]$ 存在，说明以 $j$ 结尾、公差为 $d$ 的等差子序列可以扩展到 $i$，所以 $dp[i][d] += dp[j][d] + 1$。
5. 这里 $+1$ 是因为 $[nums[j], nums[i]]$ 本身就是一个长度为 $2$ 的序列，可以形成新的等差子序列。
6. 最终答案是所有 $dp[i][d]$ 中长度至少为 $3$ 的等差子序列数目的总和。

思路 1：代码

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 3:
            return 0
        
        # dp[i][d] 表示以位置 i 结尾，公差为 d 的等差子序列的数目
        dp = [{} for _ in range(n)]
        result = 0
        
        # 遍历所有位置
        for i in range(n):
            # 遍历所有前面的位置
            for j in range(i):
                # 计算公差
                diff = nums[i] - nums[j]
                
                # 如果 j 位置存在以 diff 为公差的等差子序列
                if diff in dp[j]:
                    # 可以扩展到 i 位置，形成新的等差子序列
                    dp[i][diff] = dp[i].get(diff, 0) + dp[j][diff] + 1
                    # 累加到结果中（dp[j][diff] 表示长度至少为 3 的等差子序列）
                    result += dp[j][diff]
                else:
                    # 如果 j 位置不存在以 diff 为公差的等差子序列
                    # 那么 [nums[j], nums[i]] 是一个长度为 2 的序列
                    dp[i][diff] = dp[i].get(diff, 0) + 1
        
        return result

思路 1：复杂度分析

• 时间复杂度：$O(n^2)$，其中 $n$ 是数组的长度。需要遍历所有位置对 $(i, j)$，其中 $j < i$。
• 空间复杂度：$O(n^2)$，其中 $n$ 是数组的长度。最坏情况下，每个位置可能对应 $O(n)$ 个不同的公差，所以总空间复杂度为 $O(n^2)$。