LeetCode 1218. 最长定差子序列

约 4 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 字节
标签
数组 哈希表 动态规划

题目描述

✅ 1218. 最长定差子序列

image-20260929075322416

题意分析

在原数组中选择若干元素，保留它们的先后顺序，使所选序列每个后项减去前项都等于给定的 difference，求能得到的最大长度。

子序列不要求连续，可以跳过不合适的元素，但不能排序后重新选择。公差可以为正、零或负；公差为零时，就是寻找尽可能多次按顺序出现的同一个值。

解法：哈希表动态规划

核心思路

[!blue]

普通等差子序列可能需要枚举很多前驱，但这里公差已经固定。若当前值为 v，它前面紧邻的所选元素只能是 v - difference，因此可以按结尾值维护状态，直接定位唯一的前驱值。

定义 dp[v] 表示已经扫描过的前缀中，以数值 v 结尾的最长合法子序列长度。处理当前元素前，表中只包含更早位置。查询 dp[v - difference] 后加一，就得到用当前元素接在最佳前驱后面的长度；前驱不存在时按零处理，当前元素单独形成长度一。

同一个值多次出现时，为什么能够直接写回，而不与旧 dp[v] 再取最大值？前驱状态随扫描只会变好或不变，之前出现的 v 能使用的前驱，现在仍然可以使用。因此本次计算出的长度不会短于旧状态。公差为零时，读取的就是旧 dp[v]，再加一后覆盖同一键，恰好延长同值序列。

所有更新都遵循先读旧状态、再写当前状态，保证当前数组位置只被使用一次。不相关元素也不会清空已有状态，因为后面仍可能跨过它们接上这条子序列。

用独立的 answer 记录所有结尾值中的最大长度。最后读到的元素可能与任何长序列无关，不能直接把最后一次状态当作全局答案。

解题步骤

  1. 初始化空哈希表和全局最大长度零。
  2. 按原数组顺序读取当前值，先计算 length = dp[value - difference] + 1，缺失键视为零。
  3. 将 length 写入 dp[value]，再更新全局最大长度。
  4. 扫描结束后返回全局答案。

代码实现

class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        Map<Integer, Integer> dp = new HashMap<>();
        int answer = 0;

        for (int value : arr) {
            // 先读取前缀旧状态；公差为零时前驱键和当前键相同。
            int length = dp.getOrDefault(value - difference, 0) + 1;

            // 写回以当前值结尾的最长长度，再更新全局答案。
            dp.put(value, length);
            answer = Math.max(answer, length);
        }

        return answer;
    }
}

func longestSubsequence(arr []int, difference int) int {
    dp := make(map[int]int)
    answer := 0

    for _, value := range arr {
        // 先读取前缀旧状态；公差为零时前驱键和当前键相同。
        length := dp[value-difference] + 1
        // 写回以当前值结尾的最长长度，再更新全局答案。
        dp[value] = length
        if length > answer {
            answer = length
        }
    }
    return answer
}

复杂度分析

  • 时间复杂度：期望 $O(n)$，每个元素只进行固定次数的哈希查询和更新。
  • 空间复杂度：$O(u+1)$，其中 u 为数组中不同数值的数量，每个结尾值只保存一个最优长度。

关键点总结

[!green]

  • 固定公差使前驱值唯一，状态可以从历史下标压缩为结尾数值。
  • 状态同时包含已扫描前缀的限制和以某值结尾的要求，按原顺序更新才能满足子序列条件。
  • 前驱最优状态不下降，因此重复结尾值的直接覆盖不会丢掉更好的旧答案。

易错点总结

[!yellow]

  • 先覆盖当前键再查询前驱，公差为零时会破坏需要读取的旧状态。
  • 查询 v + difference，会把相邻项的差方向颠倒，应查前驱 v - difference。
  • 为了寻找等差关系先排序数组，会改变原来的下标先后，得到的可能不是合法子序列。
  • 遇到不匹配元素就重置状态，会把子序列错误当成必须连续的子数组。
  • 只返回最后处理的状态，可能漏掉更早结束或以其他值结尾的最长序列。

相似题目

题目 难度 关联与区别
1027. 最长等差数列 中等 公差固定后，可直接按数值查前驱v-d，本题不必为每个末项保存所有可能公差。
300. 最长递增子序列 中等 同样按已处理前缀更新最长链，本题前驱值唯一确定，原题允许所有更小值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/38406455
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！