最长定差子序列

字数 2926 2025-11-06 12:40:04

最长定差子序列

题目描述

给定一个整数数组 arr 和一个整数 difference，返回 arr 中最长定差子序列的长度。定差子序列是指一个子序列，其中相邻元素之间的差等于给定的 difference。例如，difference = 1，那么子序列 [1,2,3,4] 就是一个定差子序列。

注意：子序列不要求连续，但顺序必须与原数组保持一致。

解题过程

问题分析
我们需要找到最长的子序列，使得这个子序列中相邻两个元素的差是一个固定的值 difference。这与经典的最长递增子序列（LIS）问题类似，但有一个关键的不同点：在 LIS 中，我们关心的是当前元素能够接在哪个比它小的元素后面，从而形成更长的序列，但“比它小”这个条件比较宽泛。而在这里，条件非常具体：当前元素必须比前一个元素恰好大 difference。这个严格的条件为我们优化算法提供了可能。
动态规划状态定义
最直观的想法是定义一个一维动态规划数组 dp。
- dp[i] 表示以第 i 个元素 arr[i] 结尾的最长定差子序列的长度。
- 为什么是以 arr[i] 结尾？因为这样我们才能方便地进行状态转移。当我们考虑 arr[i] 时，我们需要知道它前面有哪些元素可以接在它前面。
状态转移方程（基础思路）
根据状态定义，对于当前位置 i，我们需要遍历它之前的所有位置 j (0 <= j < i)，检查是否存在一个元素 arr[j]，使得 arr[i] - arr[j] == difference。
- 如果存在这样的 j，那么说明 arr[i] 可以接在 arr[j] 后面，形成一个更长的子序列。因此，dp[i] = dp[j] + 1。如果有多个 j 满足条件，我们应该取最大的 dp[j] 来保证序列最长，即 dp[i] = max(dp[j]) + 1（对所有满足 arr[i] - arr[j] == difference 的 j）。
- 如果不存在这样的 j，那么 arr[i] 自己就构成一个长度为 1 的子序列，所以 dp[i] = 1。
这个思路是完全正确的，但它的时间复杂度是 O(n²)，因为对于每个 i，我们都需要遍历所有 j < i。当数组很大时，效率会很低。
优化状态转移（核心思路）
我们注意到，条件 arr[i] - arr[j] == difference 等价于 arr[j] == arr[i] - difference。
这意味着，对于当前元素 arr[i]，能接在它前面的那个元素的值是唯一确定的，就是 prev = arr[i] - difference。
我们并不需要关心这个 prev 值在数组中的哪个位置 j，我们只关心一点：以这个 prev 值结尾的最长定差子序列的长度是多少？ 如果我知道了这个长度，那么 dp[i] 直接等于这个长度加 1 就可以了。

那么，我们如何快速知道“以某个特定数值 x 结尾的最长定差子序列的长度”呢？
我们可以使用一个哈希表（比如 Python 的字典 dictionary，C++ 的 unordered_map，Java 的 HashMap）来存储这个信息。
- 重新定义状态（逻辑上）：我们实际上将状态从“以索引 i 结尾”优化为了“以数值 num 结尾”。哈希表 dp_map 的键（key）是数组中出现过的某个数值 num，值（value）就是以这个数值 num 结尾的最长定差子序列的长度。
优化后的算法步骤
- 初始化：创建一个空的哈希表 dp_map。初始化最终结果 ans = 0。
- 遍历数组：对于数组中的每一个元素 num：
  - 计算它期望的前一个元素的值：prev = num - difference。
  - 检查 prev 是否存在于哈希表 dp_map 中。
    - 如果存在，说明 num 可以接在值为 prev 的元素后面。那么以 num 结尾的最长序列长度就是 dp_map[prev] + 1。
    - 如果不存在，说明 num 是它所在序列的开头，那么长度就是 1。
  - 用这个计算出的长度更新哈希表：dp_map[num] = dp_map.get(prev, 0) + 1。这里 dp_map.get(prev, 0) 的意思是获取 prev 对应的值，如果 prev 不存在，则返回默认值 0。
  - 同时，更新全局最大值 ans = max(ans, dp_map[num])。
- 返回结果：遍历结束后，返回 ans。

举例说明
假设 arr = [1, 5, 3, 7, 5, 9], difference = 2。

当前 num	prev = num - 2	dp_map 初始状态	新长度计算	更新后的 dp_map	ans
1	-1	{}	`dp_map.get(-1, 0) + 1 = 1`	{1: 1}	1
5	3	{1: 1}	`dp_map.get(3, 0) + 1 = 1`	{1:1, 5:1}	1
3	1	{1:1, 5:1}	`dp_map[1] + 1 = 2`	{1:1, 5:1, 3:2}	2
7	5	{1:1, 5:1, 3:2}	`dp_map[5] + 1 = 2`	{1:1, 5:1, 3:2, 7:2}	2
5	3	{1:1, 5:1, 3:2, 7:2}	`dp_map[3] + 1 = 3`	{1:1, 5:3, 3:2, 7:2}	3
9	7	{1:1, 5:3, 3:2, 7:2}	`dp_map[7] + 1 = 3`	{1:1, 5:3, 3:2, 7:2, 9:3}	3

最终得到的最长定差子序列是 [1, 3, 5, 7, 9] 吗？注意，虽然数字都出现了，但顺序不对。实际上，根据我们的算法，我们找到的序列是 [1, 3, 5]（对应索引 0, 2, 4）或者 [3, 5, 7]（如果 3 前面有 1）等，长度为 3。这个结果是符合数组顺序的。

复杂度分析
- 时间复杂度：O(n)。我们只需要遍历一次数组，每次在哈希表中的操作（查找、插入、更新）平均时间复杂度都是 O(1)。
- 空间复杂度：O(n)。哈希表最多存储 n 个键值对。

总结
这道题的核心在于利用“定差”这一严格条件，将“寻找特定索引”的问题转化为“寻找特定数值”的问题。通过使用哈希表记录以每个数值结尾的最优解，我们避免了 O(n²) 的遍历，将时间复杂度成功优化到了 O(n)。这是一种典型的“以空间换时间”的优化策略。

最长定差子序列题目描述给定一个整数数组 arr 和一个整数 difference，返回 arr 中最长定差子序列的长度。定差子序列是指一个子序列，其中相邻元素之间的差等于给定的 difference。例如，difference = 1，那么子序列 [ 1,2,3,4 ] 就是一个定差子序列。注意：子序列不要求连续，但顺序必须与原数组保持一致。解题过程问题分析我们需要找到最长的子序列，使得这个子序列中相邻两个元素的差是一个固定的值 difference。这与经典的最长递增子序列（LIS）问题类似，但有一个关键的不同点：在 LIS 中，我们关心的是当前元素能够接在哪个比它小的元素后面，从而形成更长的序列，但“比它小”这个条件比较宽泛。而在这里，条件非常具体：当前元素必须比前一个元素恰好大 difference 。这个严格的条件为我们优化算法提供了可能。动态规划状态定义最直观的想法是定义一个一维动态规划数组 dp。 dp[i] 表示以第 i 个元素 arr[ i] 结尾的最长定差子序列的长度。为什么是以 arr[i] 结尾？因为这样我们才能方便地进行状态转移。当我们考虑 arr[i] 时，我们需要知道它前面有哪些元素可以接在它前面。状态转移方程（基础思路）根据状态定义，对于当前位置 i，我们需要遍历它之前的所有位置 j (0 <= j < i)，检查是否存在一个元素 arr[ j]，使得 arr[i] - arr[j] == difference 。如果存在这样的 j，那么说明 arr[ i] 可以接在 arr[ j] 后面，形成一个更长的子序列。因此， dp[i] = dp[j] + 1 。如果有多个 j 满足条件，我们应该取最大的 dp[j] 来保证序列最长，即 dp[i] = max(dp[j]) + 1 （对所有满足 arr[i] - arr[j] == difference 的 j）。如果不存在这样的 j，那么 arr[ i] 自己就构成一个长度为 1 的子序列，所以 dp[i] = 1 。这个思路是完全正确的，但它的时间复杂度是 O(n²)，因为对于每个 i，我们都需要遍历所有 j < i。当数组很大时，效率会很低。优化状态转移（核心思路）我们注意到，条件 arr[i] - arr[j] == difference 等价于 arr[j] == arr[i] - difference 。这意味着，对于当前元素 arr[ i]，能接在它前面的那个元素的值是唯一确定的，就是 prev = arr[i] - difference 。我们并不需要关心这个 prev 值在数组中的哪个位置 j，我们只关心一点：以这个 prev 值结尾的最长定差子序列的长度是多少？如果我知道了这个长度，那么 dp[i] 直接等于这个长度加 1 就可以了。那么，我们如何快速知道“以某个特定数值 x 结尾的最长定差子序列的长度”呢？我们可以使用一个哈希表（比如 Python 的字典 dictionary，C++ 的 unordered_ map，Java 的 HashMap）来存储这个信息。重新定义状态（逻辑上）：我们实际上将状态从“以索引 i 结尾”优化为了“以数值 num 结尾”。哈希表 dp_map 的键（key）是数组中出现过的某个数值 num ，值（value）就是以这个数值 num 结尾的最长定差子序列的长度。优化后的算法步骤初始化：创建一个空的哈希表 dp_map 。初始化最终结果 ans = 0 。遍历数组：对于数组中的每一个元素 num ：计算它期望的前一个元素的值： prev = num - difference 。检查 prev 是否存在于哈希表 dp_map 中。如果存在，说明 num 可以接在值为 prev 的元素后面。那么以 num 结尾的最长序列长度就是 dp_map[prev] + 1 。如果不存在，说明 num 是它所在序列的开头，那么长度就是 1。用这个计算出的长度更新哈希表： dp_map[num] = dp_map.get(prev, 0) + 1 。这里 dp_map.get(prev, 0) 的意思是获取 prev 对应的值，如果 prev 不存在，则返回默认值 0。同时，更新全局最大值 ans = max(ans, dp_map[num]) 。返回结果：遍历结束后，返回 ans 。举例说明假设 arr = [1, 5, 3, 7, 5, 9] , difference = 2 。 | 当前 num | prev = num - 2 | dp_ map 初始状态 | 新长度计算 | 更新后的 dp_ map | ans | | :--- | :--- | :--- | :--- | :--- | :--- | | 1 | -1 | {} | dp_map.get(-1, 0) + 1 = 1 | {1: 1} | 1 | | 5 | 3 | {1: 1} | dp_map.get(3, 0) + 1 = 1 | {1:1, 5:1 } | 1 | | 3 | 1 | {1:1, 5:1} | dp_map[1] + 1 = 2 | {1:1, 5:1, 3:2 } | 2 | | 7 | 5 | {1:1, 5:1, 3:2} | dp_map[5] + 1 = 2 | {1:1, 5:1, 3:2, 7:2 } | 2 | | 5 | 3 | {1:1, 5:1, 3:2, 7:2} | dp_map[3] + 1 = 3 | {1:1, 5:3 , 3:2, 7:2} | 3 | | 9 | 7 | {1:1, 5:3, 3:2, 7:2} | dp_map[7] + 1 = 3 | {1:1, 5:3, 3:2, 7:2, 9:3} | 3 | 最终得到的最长定差子序列是 [1, 3, 5, 7, 9] 吗？注意，虽然数字都出现了，但顺序不对。实际上，根据我们的算法，我们找到的序列是 [1, 3, 5] （对应索引 0, 2, 4）或者 [3, 5, 7] （如果 3 前面有 1）等，长度为 3。这个结果是符合数组顺序的。复杂度分析时间复杂度：O(n)。我们只需要遍历一次数组，每次在哈希表中的操作（查找、插入、更新）平均时间复杂度都是 O(1)。空间复杂度：O(n)。哈希表最多存储 n 个键值对。总结这道题的核心在于利用“定差”这一严格条件，将“寻找特定索引”的问题转化为“寻找特定数值”的问题。通过使用哈希表记录以每个数值结尾的最优解，我们避免了 O(n²) 的遍历，将时间复杂度成功优化到了 O(n)。这是一种典型的“以空间换时间”的优化策略。