LeetCode 1218. 最长定差子序列

2022-02-28 HGNULB 约 5 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 1218. 最长定差子序列

题意分析

要的是一个长度，不需要还原具体的子序列。子序列意味着元素可以不连续，但必须保持原数组中的先后顺序。

「相邻两项之差恰好等于 difference」这个条件比一般的等差子序列强得多：公差是题目给死的常量，不需要枚举。这意味着一旦确定了子序列的最后一个元素值 x，它前面那个元素的值只能是 x - difference，唯一确定，没有任何选择空间。

数组长度上限 $10^5$，明确排除了 $O(n^2)$ 的两两比较。而元素值域是 $[-10^4, 10^4]$、difference 在 $[-10^4, 10^4]$，说明「按值索引」是可行的——值的种类是有限且可枚举的，可以直接把值当作下标或键来用。

注意 difference 可以为 0 和负数。为 0 时子序列就是同一个值的重复出现，为负时序列递减，这两种情况不能被特判掉，必须被统一的逻辑覆盖。

边界：数组只有一个元素（答案恒为 1）、difference 为 0、数组中存在重复值、所有元素互不相关（答案为 1）。

解法：哈希表动态规划

核心思路

公差固定后，值 v 的前驱值只能是 v - difference。因此无需枚举前面的所有下标，只需记住“此前以某个值结尾的最长长度”，用哈希表即可在均摊常数时间找到唯一前驱。

定义 dp[x]：扫描完当前前缀后，以值 x 结尾、相邻差恒为 difference 的最长子序列长度。处理 v 前，表中只包含当前位置左侧的状态；转移为 dp[v] = dp[v - difference] + 1，不存在前驱时长度从 1 开始。

同一个值再次出现时，前驱状态只会保持或变长，所以可直接覆盖 dp[v]。difference = 0 时前驱和当前键相同，必须先读取旧值再写回，才能让相同元素逐个接长。

正确性说明：按下标归纳。处理 v 时，任何以它结尾的合法子序列倒数第二项都必须等于 v - difference，其最长前缀长度已由状态定义保存在哈希表中；在该序列后接上 v 得到的长度可达，因此转移既不会漏掉更优解，也不会构造非法序列。对所有结尾长度取最大值，就是全局最长答案。

解题步骤

初始化空哈希表 dp 与 answer = 0。

从左到右遍历每个值 v，先读取 dp[v - difference]，不存在时按 0 处理。

令 length = dp[v - difference] + 1，再写入 dp[v]，并更新全局最大值。

遍历结束后返回 answer。

例如 arr = [1,5,7,8,5,3,4,2,1]、difference = -2，状态依次形成 7 → 5 → 3 → 1，答案为 4。difference = 0、arr = [1,1,1] 时，同一键的旧值依次为 0、1、2，最终得到 3；负数值也可直接作为哈希键，无需偏移。

代码实现

import java.util.HashMap;
import java.util.Map;

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(n)$。哈希表最多保存 n 个不同值的状态。

关键点总结

固定公差使前驱值唯一，状态可以从“下标”降维成“结尾值”。

dp[x] 必须包含“已扫描前缀”和“以 x 结尾”两层语义，才能保证下标顺序合法。

从左到右扫描并先读后写，尤其保证 difference = 0 时能接到上一次出现的相同值。

子序列不要求连续；中间不相关的元素不会清空任何状态。

易错点总结

把前驱写成 value + difference：arr = [1,3,5]、difference = 2 时找不到 1、3 作为前驱，错误返回 1；应查 value - difference。

先覆盖 dp[value] 再读取前驱：difference = 0、arr = [1,1,1] 时会读到本轮新值，状态含义被破坏。必须先读旧状态。

从右向左扫描：同一用例 [1,3,5] 会让状态来自当前位置右侧，无法构成保持原下标顺序的子序列。

把子序列当成连续子数组：arr = [1,100,3]、difference = 2 的正确答案是子序列 [1,3]，不能因 100 不匹配就清空长度。

使用未偏移的数组按值索引：arr = [-1,-3] 会访问负下标；值域含负数时哈希表最直接。

只返回最后一次转移长度：arr = [1,3,5,2]、difference = 2 的全局答案是 3，最后一个值的状态却只有 1，必须在线维护最大值。

相似题目

题目	难度	考察点
300. 最长递增子序列	中等	前驱不唯一，必须在所有更小的前驱里取最大值
413. 等差数列划分	中等	要求连续子数组且统计个数，转移退化成一维递推
1027. 最长等差数列	中等	公差未知需要并入状态，状态升到二维 `dp[i][d]`
446. 等差数列划分 II - 子序列	困难	统计弱等差序列数量，需处理长度为 2 的中间态不计数