最长定差子序列

字数 2506 2025-10-30 21:15:36

最长定差子序列

题目描述
给定一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于给定的 difference。

例如：
输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2
输出：4
解释：最长的等差子序列是 [7,5,3,1]，相邻元素差为 -2。

解题过程

这个问题是经典的最长递增子序列（LIS）问题的一个变种，但有一个重要的简化：公差是固定的。这意味着，对于序列中的任意一个元素，它的前一个元素（如果存在的话）是唯一确定的。这个特性让我们可以使用一种更高效的动态规划方法。

动态规划状态定义
我们定义 dp[x] 表示：以数值 x 结尾的、公差为 difference 的最长等差子序列的长度。
这里的状态表示与传统的以“数组索引”为状态不同，而是以“数值”本身作为状态。这利用了题目中“固定公差”的特性。
状态转移方程
思考一下，如果一个等差子序列要以当前的数字 x 结尾，那么在这个序列中，紧挨在 x 前面的那个数字应该是多少？
根据公差的定义，它应该是 x - difference。
因此，以 x 结尾的最长序列长度，就是在以 x - difference 结尾的最长序列长度基础上加 1。
状态转移方程可以写为：
dp[x] = dp[x - difference] + 1

这个方程的含义是：如果存在一个以 x-difference 结尾的序列，那么我们可以把 x 接在这个序列的后面，形成一个更长的序列。如果不存在这样的序列（即 dp[x-difference] 尚未被定义），那么 x 本身可以构成一个长度为 1 的序列。
初始状态
初始时，我们可以认为每个数字自身都至少可以构成一个长度为 1 的等差子序列。所以，当我们第一次遇到一个数字 x 时，我们可以将 dp[x] 初始化为 1。
计算顺序与高效实现
我们只需要顺序遍历给定的数组 arr。对于遍历到的每个数字 num：
- 查看是否存在键为 num - difference 的状态。
- 如果存在，则 dp[num] = dp[num - difference] + 1。
- 如果不存在，则 dp[num] = 1。
- 同时，更新我们找到的最大长度。
为了高效地存储和查询这些以数值为键的状态，我们最自然的选择就是使用哈希表（在 Python 中是 dict，在 C++ 中是 unordered_map，在 Java 中是 HashMap）。
举例说明
让我们用题目中的例子来走一遍流程：arr = [1,5,7,8,5,3,4,2,1], difference = -2。

我们初始化一个空的哈希表 dp 和一个变量 max_length = 0。
- 遍历到 1：计算前驱 1 - (-2) = 3。dp 中无键 3，所以 dp[1] = 1。max_length = max(0, 1) = 1。
  dp 状态: {1: 1}
- 遍历到 5：前驱 5 - (-2) = 7。无键 7，所以 dp[5] = 1。max_length = 1。
  dp 状态: {1:1, 5:1}
- 遍历到 7：前驱 7 - (-2) = 9。无键 9，所以 dp[7] = 1。max_length = 1。
  dp 状态: {1:1, 5:1, 7:1}
- 遍历到 8：前驱 8 - (-2) = 10。无键 10，所以 dp[8] = 1。max_length = 1。
  dp 状态: {1:1, 5:1, 7:1, 8:1}
- 遍历到 5：前驱 5 - (-2) = 7。dp 中存在键 7，其值为 1。所以 dp[5] = dp[7] + 1 = 1 + 1 = 2。max_length = max(1, 2) = 2。
  dp 状态更新: {1:1, 5:2, 7:1, 8:1} (注意，dp[5] 从 1 更新为 2)
- 遍历到 3：前驱 3 - (-2) = 5。dp 中存在键 5，其值现在是 2。所以 dp[3] = dp[5] + 1 = 2 + 1 = 3。max_length = max(2, 3) = 3。
  dp 状态: {1:1, 5:2, 7:1, 8:1, 3:3}
- 遍历到 4：前驱 4 - (-2) = 6。无键 6，所以 dp[4] = 1。max_length = 3。
  dp 状态: { ... , 4:1}
- 遍历到 2：前驱 2 - (-2) = 4。dp 中存在键 4，其值为 1。所以 dp[2] = dp[4] + 1 = 1 + 1 = 2。max_length = 3。
  dp 状态: { ... , 2:2}
- 遍历到 1：前驱 1 - (-2) = 3。dp 中存在键 3，其值为 3。所以 dp[1] = dp[3] + 1 = 3 + 1 = 4。max_length = max(3, 4) = 4。
  dp 状态更新: {1:4, 5:2, 7:1, 8:1, 3:3, 4:1, 2:2}
最终得到的最长长度是 4，对应的序列通过反向追踪可知是 7->5->3->1。
算法总结
- 时间复杂度：O(n)，其中 n 是数组 arr 的长度。我们只需要遍历数组一次，每次哈希表的插入和查询操作都可以认为是 O(1) 的时间复杂度。
- 空间复杂度：O(n)，哈希表在最坏情况下需要存储 n 个键值对。

这种方法巧妙地利用了固定公差这一条件，将问题转化为了一个依赖关系非常明确的动态规划问题，并通过哈希表实现了高效求解。

最长定差子序列题目描述给定一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于给定的 difference。例如：输入：arr = [ 1,5,7,8,5,3,4,2,1 ], difference = -2 输出：4 解释：最长的等差子序列是 [ 7,5,3,1 ]，相邻元素差为 -2。解题过程这个问题是经典的最长递增子序列（LIS）问题的一个变种，但有一个重要的简化：公差是固定的。这意味着，对于序列中的任意一个元素，它的前一个元素（如果存在的话）是唯一确定的。这个特性让我们可以使用一种更高效的动态规划方法。动态规划状态定义我们定义 dp[x] 表示：以数值 x 结尾的、公差为 difference 的最长等差子序列的长度。这里的状态表示与传统的以“数组索引”为状态不同，而是以“数值”本身作为状态。这利用了题目中“固定公差”的特性。状态转移方程思考一下，如果一个等差子序列要以当前的数字 x 结尾，那么在这个序列中，紧挨在 x 前面的那个数字应该是多少？根据公差的定义，它应该是 x - difference 。因此，以 x 结尾的最长序列长度，就是在以 x - difference 结尾的最长序列长度基础上加 1。状态转移方程可以写为： dp[x] = dp[x - difference] + 1 这个方程的含义是：如果存在一个以 x-difference 结尾的序列，那么我们可以把 x 接在这个序列的后面，形成一个更长的序列。如果不存在这样的序列（即 dp[x-difference] 尚未被定义），那么 x 本身可以构成一个长度为 1 的序列。初始状态初始时，我们可以认为每个数字自身都至少可以构成一个长度为 1 的等差子序列。所以，当我们第一次遇到一个数字 x 时，我们可以将 dp[x] 初始化为 1。计算顺序与高效实现我们只需要顺序遍历给定的数组 arr 。对于遍历到的每个数字 num ：查看是否存在键为 num - difference 的状态。如果存在，则 dp[num] = dp[num - difference] + 1 。如果不存在，则 dp[num] = 1 。同时，更新我们找到的最大长度。为了高效地存储和查询这些以数值为键的状态，我们最自然的选择就是使用哈希表（在 Python 中是 dict ，在 C++ 中是 unordered_map ，在 Java 中是 HashMap ）。举例说明让我们用题目中的例子来走一遍流程： arr = [1,5,7,8,5,3,4,2,1] , difference = -2 。我们初始化一个空的哈希表 dp 和一个变量 max_length = 0 。遍历到 1 ：计算前驱 1 - (-2) = 3 。 dp 中无键 3 ，所以 dp[1] = 1 。 max_length = max(0, 1) = 1 。 dp 状态: {1: 1} 遍历到 5 ：前驱 5 - (-2) = 7 。无键 7 ，所以 dp[5] = 1 。 max_length = 1 。 dp 状态: {1:1, 5:1} 遍历到 7 ：前驱 7 - (-2) = 9 。无键 9 ，所以 dp[7] = 1 。 max_length = 1 。 dp 状态: {1:1, 5:1, 7:1} 遍历到 8 ：前驱 8 - (-2) = 10 。无键 10 ，所以 dp[8] = 1 。 max_length = 1 。 dp 状态: {1:1, 5:1, 7:1, 8:1} 遍历到 5 ：前驱 5 - (-2) = 7 。 dp 中存在键 7 ，其值为 1 。所以 dp[5] = dp[7] + 1 = 1 + 1 = 2 。 max_length = max(1, 2) = 2 。 dp 状态更新: {1:1, 5:2, 7:1, 8:1} (注意， dp[5] 从 1 更新为 2) 遍历到 3 ：前驱 3 - (-2) = 5 。 dp 中存在键 5 ，其值现在是 2 。所以 dp[3] = dp[5] + 1 = 2 + 1 = 3 。 max_length = max(2, 3) = 3 。 dp 状态: {1:1, 5:2, 7:1, 8:1, 3:3} 遍历到 4 ：前驱 4 - (-2) = 6 。无键 6 ，所以 dp[4] = 1 。 max_length = 3 。 dp 状态: { ... , 4:1} 遍历到 2 ：前驱 2 - (-2) = 4 。 dp 中存在键 4 ，其值为 1 。所以 dp[2] = dp[4] + 1 = 1 + 1 = 2 。 max_length = 3 。 dp 状态: { ... , 2:2} 遍历到 1 ：前驱 1 - (-2) = 3 。 dp 中存在键 3 ，其值为 3 。所以 dp[1] = dp[3] + 1 = 3 + 1 = 4 。 max_length = max(3, 4) = 4 。 dp 状态更新: {1:4, 5:2, 7:1, 8:1, 3:3, 4:1, 2:2} 最终得到的最长长度是 4，对应的序列通过反向追踪可知是 7->5->3->1。算法总结时间复杂度：O(n)，其中 n 是数组 arr 的长度。我们只需要遍历数组一次，每次哈希表的插入和查询操作都可以认为是 O(1) 的时间复杂度。空间复杂度：O(n)，哈希表在最坏情况下需要存储 n 个键值对。这种方法巧妙地利用了固定公差这一条件，将问题转化为了一个依赖关系非常明确的动态规划问题，并通过哈希表实现了高效求解。