最长等差数列划分 II

最长等差数列划分 II - 子序列

字数 3286 2025-12-24 06:46:57

最长等差数列划分 II - 子序列

题目描述

给定一个整数数组 nums，返回数组中等差子序列的数目。如果一个序列中 至少有三个元素，并且任意两个相邻元素之间的差值相同，则称该序列为等差序列。例如，[1, 3, 5, 7, 9]、[7, 7, 7, 7] 和 [3, -1, -5, -9] 都是等差序列。
注意：子序列是由数组通过删除一些元素（也可以不删除）得到，不改变剩余元素的相对顺序。也就是说，本题关注的是等差子序列（不要求连续），而不仅仅是连续的子数组。

例如：

输入：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]

解题思路

这是一个经典的线性动态规划问题，核心在于如何高效地统计所有长度至少为3的等差子序列。由于子序列不要求连续，直接枚举所有子序列会超时（复杂度 O(2^n)），我们需要设计一个 DP 状态来记录以某个位置结尾、具有特定公差的等差子序列的数量。

关键观察

等差子序列可以由更短的等差子序列扩展而来。例如，如果已知一个以 nums[j] 结尾、公差为 d 的等差子序列，且当前元素 nums[i] 与 nums[j] 的差值也是 d，那么就可以将 nums[i] 接在后面，形成一个新的等差子序列。
长度为2的“弱等差”序列（只有两个元素）是构建更长序列的基础。但题目要求长度至少为3，所以在统计答案时，我们只统计长度≥3的序列。

状态定义

我们使用一个二维动态规划表 dp[i][d]，表示以 nums[i] 结尾、公差为 d 的等差子序列的数量。但公差 d 可能很大（例如差值可能达到 ±2^31），因此不能直接用数组索引。我们可以使用一个字典（哈希表）列表，其中 dp[i] 是一个字典，键为公差 d，值为以 nums[i] 结尾、公差为 d 的等差子序列的数量（包括长度为2的序列）。

更精确地说，我们定义：

dp[i] 是一个哈希表，映射公差 d 到以 nums[i] 结尾、公差为 d 的等差子序列的个数（这些序列长度至少为2）。
在统计答案时，我们只累加那些长度≥3的序列。因此，当我们考虑 (j, i) 对时，如果 nums[i] 可以和以 nums[j] 结尾、公差为 d 的序列形成更长的序列，那么新增加的序列数量就是 dp[j][d]（因为 dp[j][d] 中每个序列加上 nums[i] 都形成一个长度≥3的序列）。

详细步骤

初始化：
- 令 n = len(nums)。
- 初始化一个列表 dp，长度为 n，每个元素是一个空字典（或 defaultdict(int)）。
- 初始化答案 ans = 0。
遍历所有对 (j, i)（其中 0 ≤ j < i < n）：
- 计算公差 d = nums[i] - nums[j]。
- 查看 dp[j] 中是否已有公差为 d 的序列：
  - 如果存在，则 cnt = dp[j][d] 表示以 nums[j] 结尾、公差为 d 的序列个数（每个序列长度至少为2）。
  - 将这些序列后面加上 nums[i]，就得到了 cnt 个长度至少为3的等差子序列，所以 ans += cnt。
- 然后，我们需要更新 dp[i][d]：
  - 对于当前对 (j, i)，它们本身可以形成一个长度为2的弱等差序列（公差为 d）。所以，我们应该在 dp[i][d] 中增加一个计数，表示以 nums[i] 结尾、公差为 d 的长度为2的序列。
  - 此外，如果 dp[j] 中有公差为 d 的序列（个数为 cnt），那么这些序列加上 nums[i] 后，也形成了以 nums[i] 结尾、公差为 d 的序列，且长度至少为3。因此，dp[i][d] 还需要加上 cnt。
  - 综合起来，dp[i][d] += dp[j].get(d, 0) + 1。
    - 这里的 +1 对应长度为2的序列 (nums[j], nums[i])。
    - dp[j].get(d, 0) 对应从以 nums[j] 结尾的序列扩展而来的更长的序列。
返回答案：
- 遍历结束后，ans 即为所有长度至少为3的等差子序列的个数。

举例说明

以 nums = [2, 4, 6, 8] 为例：

i=0：dp[0] 为空。
i=1（nums[1]=4）：
- j=0：d=4-2=2。dp[0] 中没有公差2，所以 cnt=0，ans 不变。更新 dp[1][2] = 0 + 1 = 1（表示序列 [2,4]）。
i=2（nums[2]=6）：
- j=0：d=6-2=4。dp[0] 中没有公差4，更新 dp[2][4] = 0 + 1 = 1（序列 [2,6]）。
- j=1：d=6-4=2。dp[1] 中有公差2，cnt = dp[1][2] = 1（对应序列 [2,4]）。将 6 接在后面得到 [2,4,6]，长度≥3，所以 ans += 1 = 1。更新 dp[2][2] = dp[1][2] + 1 = 1 + 1 = 2（其中 1 来自 [2,4,6]，另一个 1 来自长度为2的序列 [4,6]）。
i=3（nums[3]=8）：
- j=0：d=8-2=6。更新 dp[3][6] = 0 + 1 = 1（序列 [2,8]）。
- j=1：d=8-4=4。dp[1] 中没有公差4，更新 dp[3][4] = 0 + 1 = 1（序列 [4,8]）。
- j=2：d=8-6=2。dp[2] 中有公差2，cnt = dp[2][2] = 2（对应序列 [2,4,6] 和 [4,6]）。将 8 接在后面：
  - 从 [2,4,6] 得到 [2,4,6,8]（长度≥3）。
  - 从 [4,6] 得到 [4,6,8]（长度≥3）。
    所以 ans += 2 = 3。更新 dp[3][2] = dp[2][2] + 1 = 2 + 1 = 3（其中 2 来自上述两个扩展序列，1 来自长度为2的序列 [6,8]）。

最终 ans = 3，对应 [2,4,6]、[2,4,6,8]、[4,6,8]。注意，这里没有包括 [6,8] 因为长度只有2，也不包括 [2,6,8] 因为 2,6,8 不是等差数列（公差分别为4和2）。实际上，对于 [2,4,6,8]，它包含了三个长度≥3的子序列：[2,4,6]、[4,6,8]、[2,4,6,8]，所以总共是3个。

复杂度分析

时间复杂度：O(n²)，因为需要遍历所有对 (j, i)，每次操作字典的复杂度平均为 O(1)。
空间复杂度：O(n²)，最坏情况下每个 dp[i] 可能存储 O(i) 个不同的公差。

注意事项

公差 d 可能超过32位整数范围，但在大多数语言中，哈希表可以处理。
答案可能很大，可能需要使用64位整数（例如 long long 或 int64）来存储。
本题与“等差数列划分 I”（连续子数组）不同，那里只需要 O(n) 时间，而这里由于子序列不连续，需要 O(n²) 时间。

总结

这个问题的核心在于动态规划的状态设计：以每个位置结尾、以每个公差为键，记录等差序列的数量。通过从较短序列扩展，我们可以在 O(n²) 时间内统计所有长度≥3的等差子序列。

最长等差数列划分 II - 子序列题目描述给定一个整数数组 nums ，返回数组中等差子序列的数目。如果一个序列中至少有三个元素，并且任意两个相邻元素之间的差值相同，则称该序列为等差序列。例如， [1, 3, 5, 7, 9] 、 [7, 7, 7, 7] 和 [3, -1, -5, -9] 都是等差序列。注意：子序列是由数组通过删除一些元素（也可以不删除）得到，不改变剩余元素的相对顺序。也就是说，本题关注的是等差子序列（不要求连续），而不仅仅是连续的子数组。例如：输入： 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] 解题思路这是一个经典的线性动态规划问题，核心在于如何高效地统计所有长度至少为3的等差子序列。由于子序列不要求连续，直接枚举所有子序列会超时（复杂度 O(2^n)），我们需要设计一个 DP 状态来记录以某个位置结尾、具有特定公差的等差子序列的数量。关键观察等差子序列可以由更短的等差子序列扩展而来。例如，如果已知一个以 nums[j] 结尾、公差为 d 的等差子序列，且当前元素 nums[i] 与 nums[j] 的差值也是 d ，那么就可以将 nums[i] 接在后面，形成一个新的等差子序列。长度为2的“弱等差”序列（只有两个元素）是构建更长序列的基础。但题目要求长度至少为3，所以在统计答案时，我们只统计长度≥3的序列。状态定义我们使用一个二维动态规划表 dp[i][d] ，表示以 nums[i] 结尾、公差为 d 的等差子序列的数量。但公差 d 可能很大（例如差值可能达到 ±2^31），因此不能直接用数组索引。我们可以使用一个字典（哈希表）列表，其中 dp[i] 是一个字典，键为公差 d ，值为以 nums[i] 结尾、公差为 d 的等差子序列的数量（包括长度为2的序列）。更精确地说，我们定义： dp[i] 是一个哈希表，映射公差 d 到以 nums[i] 结尾、公差为 d 的等差子序列的个数（这些序列长度至少为2）。在统计答案时，我们只累加那些长度≥3的序列。因此，当我们考虑 (j, i) 对时，如果 nums[i] 可以和以 nums[j] 结尾、公差为 d 的序列形成更长的序列，那么新增加的序列数量就是 dp[j][d] （因为 dp[j][d] 中每个序列加上 nums[i] 都形成一个长度≥3的序列）。详细步骤初始化：令 n = len(nums) 。初始化一个列表 dp ，长度为 n ，每个元素是一个空字典（或 defaultdict(int) ）。初始化答案 ans = 0 。遍历所有对 (j, i) （其中 0 ≤ j < i < n ）：计算公差 d = nums[i] - nums[j] 。查看 dp[j] 中是否已有公差为 d 的序列：如果存在，则 cnt = dp[j][d] 表示以 nums[j] 结尾、公差为 d 的序列个数（每个序列长度至少为2）。将这些序列后面加上 nums[i] ，就得到了 cnt 个长度至少为3的等差子序列，所以 ans += cnt 。然后，我们需要更新 dp[i][d] ：对于当前对 (j, i) ，它们本身可以形成一个长度为2的弱等差序列（公差为 d ）。所以，我们应该在 dp[i][d] 中增加一个计数，表示以 nums[i] 结尾、公差为 d 的长度为2的序列。此外，如果 dp[j] 中有公差为 d 的序列（个数为 cnt ），那么这些序列加上 nums[i] 后，也形成了以 nums[i] 结尾、公差为 d 的序列，且长度至少为3。因此， dp[i][d] 还需要加上 cnt 。综合起来， dp[i][d] += dp[j].get(d, 0) + 1 。这里的 +1 对应长度为2的序列 (nums[j], nums[i]) 。 dp[j].get(d, 0) 对应从以 nums[j] 结尾的序列扩展而来的更长的序列。返回答案：遍历结束后， ans 即为所有长度至少为3的等差子序列的个数。举例说明以 nums = [2, 4, 6, 8] 为例： i=0 ： dp[0] 为空。 i=1 （ nums[1]=4 ）： j=0 ： d=4-2=2 。 dp[0] 中没有公差2，所以 cnt=0 ， ans 不变。更新 dp[1][2] = 0 + 1 = 1 （表示序列 [2,4] ）。 i=2 （ nums[2]=6 ）： j=0 ： d=6-2=4 。 dp[0] 中没有公差4，更新 dp[2][4] = 0 + 1 = 1 （序列 [2,6] ）。 j=1 ： d=6-4=2 。 dp[1] 中有公差2， cnt = dp[1][2] = 1 （对应序列 [2,4] ）。将 6 接在后面得到 [2,4,6] ，长度≥3，所以 ans += 1 = 1 。更新 dp[2][2] = dp[1][2] + 1 = 1 + 1 = 2 （其中 1 来自 [2,4,6] ，另一个 1 来自长度为2的序列 [4,6] ）。 i=3 （ nums[3]=8 ）： j=0 ： d=8-2=6 。更新 dp[3][6] = 0 + 1 = 1 （序列 [2,8] ）。 j=1 ： d=8-4=4 。 dp[1] 中没有公差4，更新 dp[3][4] = 0 + 1 = 1 （序列 [4,8] ）。 j=2 ： d=8-6=2 。 dp[2] 中有公差2， cnt = dp[2][2] = 2 （对应序列 [2,4,6] 和 [4,6] ）。将 8 接在后面：从 [2,4,6] 得到 [2,4,6,8] （长度≥3）。从 [4,6] 得到 [4,6,8] （长度≥3）。所以 ans += 2 = 3 。更新 dp[3][2] = dp[2][2] + 1 = 2 + 1 = 3 （其中 2 来自上述两个扩展序列， 1 来自长度为2的序列 [6,8] ）。最终 ans = 3 ，对应 [2,4,6] 、 [2,4,6,8] 、 [4,6,8] 。注意，这里没有包括 [6,8] 因为长度只有2，也不包括 [2,6,8] 因为 2,6,8 不是等差数列（公差分别为4和2）。实际上，对于 [2,4,6,8] ，它包含了三个长度≥3的子序列： [2,4,6] 、 [4,6,8] 、 [2,4,6,8] ，所以总共是3个。复杂度分析时间复杂度：O(n²)，因为需要遍历所有对 (j, i) ，每次操作字典的复杂度平均为 O(1)。空间复杂度：O(n²)，最坏情况下每个 dp[i] 可能存储 O(i) 个不同的公差。注意事项公差 d 可能超过32位整数范围，但在大多数语言中，哈希表可以处理。答案可能很大，可能需要使用64位整数（例如 long long 或 int64 ）来存储。本题与“等差数列划分 I”（连续子数组）不同，那里只需要 O(n) 时间，而这里由于子序列不连续，需要 O(n²) 时间。总结这个问题的核心在于动态规划的状态设计：以每个位置结尾、以每个公差为键，记录等差序列的数量。通过从较短序列扩展，我们可以在 O(n²) 时间内统计所有长度≥3的等差子序列。