LeetCode 219. 存在重复元素 II

约 8 分钟
文章信息 8 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 字节跳动 图森 面试经典 150 题
标签
数组 哈希表 滑动窗口
目录

题目描述

✅ 219. 存在重复元素 II

题意分析

问的是数组里是否存在两个下标 i 和 j，满足 nums[i] == nums[j] 且 abs(i - j) <= k。注意问的是存在性，返回布尔值，不需要给出具体是哪一对。

两个条件是「值相等」和「下标靠近」的合取，前者天然指向按值分组，后者天然指向对下标做距离约束，所以状态里必须同时携带值和下标两样信息。

数组长度可以到 10^5，元素值域是完整的 int 范围且可以为负，k 可以是 0，也可以远大于数组长度。k = 0 时要求 i 和 j 距离不超过 0，而题目又要求它们是不同下标，所以此时恒为 false；k 极大时等价于问「数组里是否有重复元素」。

值域跨整个 int 说明不能开值域数组做计数，只能用哈希；长度 10^5 说明 $O(n^2)$ 的两两比较会退化到 10^10 次操作，必须做到线性或近线性。

解法：哈希表记录最近位置

核心思路

暴力做法是双重循环枚举所有下标对 (i, j)，检查值是否相等且距离是否不超过 k。它显然正确，但在 10^5 长度下要做约 50 亿次比较，瓶颈在于对每一个 i，我们都从头把整个数组重扫了一遍，而其中绝大多数下标离 i 早就超过 k 了，根本没有资格参与配对。

稍微收敛一点的暴力是只往前看 k 个位置，代价变成 $O(nk)$，但 k 本身也可以到 10^5，最坏情况没有改善。真正的浪费在于：对固定的值 v，我们反复线性搜索它上一次出现在哪。

观察点是这个题的非对称性——如果把 i 固定为「当前正在处理的右端点」，那么所有候选的 j 都在 i 左边，而在所有满足 nums[j] == nums[i] 的左侧下标里，只有最大的那个才最有可能满足 i - j <= k。换句话说，同一个值的更早出现位置全是冗余的：如果最近的那次都够不着，更早的必然更够不着。

由此得到本解法的不变量：扫描到下标 i 之前，哈希表里对每个已出现过的值 v，恰好存着 v 在 [0, i-1] 范围内最后一次出现的下标。维护住这条不变量，判断就退化成一次哈希查询加一次减法。

这条不变量也顺带决定了读写顺序：必须先用当前值查表（此时表中还没有 i 自己，避免拿自己和自己配对得到距离 0），再把 i 写回去覆盖旧值（保证下一轮开始时不变量依然成立）。

解题步骤

  • 建一个从元素值到下标的哈希表 last，初始为空。之所以映射到下标而不是布尔或次数，是因为距离条件只依赖位置，只记「出现过」会丢掉判断所需的信息。
  • 从左到右用下标 i 遍历数组。之所以必须带着下标遍历而不是只遍历值，是因为距离约束的两端都是下标，值本身无法推出位置。
  • 每到一个位置，先查 last 中是否已有 nums[i]。之所以先查后写，是因为写在前面会让当前元素立刻覆盖自己的记录，随后查到的就是 i 本身，i - i = 0 <= k 在 k >= 0 时恒成立，任何输入都会被误判为 true。
  • 若查到旧下标 prev 且 i - prev <= k，立刻返回 true。之所以能立刻返回，是因为题目只问存在性，找到一对合法配对后无需继续；同时因为 prev < i，i - prev 必为正数，不必再取绝对值。
  • 无论是否查到，都把 last[nums[i]] = i 写回去。之所以在「查到了但距离超了」的情况下也要覆盖，是因为旧下标已经被证明太远，留着它只会让后续判断更悲观，而 i 是这个值到目前为止最靠右的出现位置，正是不变量要求保存的那个。
  • 循环自然结束说明没有任何合法配对，返回 false。

以 nums = [1, 2, 3, 1, 2, 3], k = 2 走一遍：i = 0，值 1，表中无，写入 {1:0}。i = 1，值 2，表中无，写入 {1:0, 2:1}。i = 2，值 3，表中无，写入 {1:0, 2:1, 3:2}。i = 3，值 1，查到 prev = 0，3 - 0 = 3 > 2，不满足，覆盖为 {1:3, 2:1, 3:2}。i = 4，值 2，查到 prev = 1，4 - 1 = 3 > 2，覆盖为 {1:3, 2:4, 3:2}。i = 5，值 3，查到 prev = 2，5 - 2 = 3 > 2，覆盖。循环结束返回 false，与预期一致。

再用 nums = [1, 0, 1, 1], k = 1 检验覆盖的必要性：i = 0 写入 {1:0}。i = 1 写入 {1:0, 0:1}。i = 2，值 1，查到 prev = 0，2 - 0 = 2 > 1，不满足，此时把记录覆盖成 {1:2, ...}。i = 3，值 1，查到 prev = 2，3 - 2 = 1 <= 1，返回 true。如果第 i = 2 步没有覆盖而是保留了最早的 0，第 i = 3 步算出的距离会是 3，就会漏掉正确答案。

代码实现

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> last = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            Integer prev = last.get(nums[i]);
            if (prev != null && i - prev <= k) {
                return true;
            }
            last.put(nums[i], i);
        }
        return false;
    }
}

func containsNearbyDuplicate(nums []int, k int) bool {
    last := make(map[int]int)
    for i, v := range nums {
        if prev, ok := last[v]; ok && i-prev <= k {
            return true
        }
        last[v] = i
    }
    return false
}

复杂度分析

  • 时间复杂度：$O(n)$，凭据是数组只被从左到右扫描一遍，每个位置上做的是一次哈希查询和一次哈希写入，两者的均摊代价都是 $O(1)$，与 k 的大小完全无关。
  • 空间复杂度：$O(\min(n, m))$，其中 $m$ 是数组中不同元素的个数，凭据是哈希表里每个不同的值只占一条记录，值重复出现时只是覆盖下标而不新增条目，最坏情况（全部互异）退化为 $O(n)$。

关键点总结

  • 「值相等 + 下标接近」这类双条件存在性问题，通用套路是把其中一个条件交给哈希表做分组，另一个条件在查表命中后用 $O(1)$ 判断来兜住。
  • 固定右端点、只回看左侧的扫描方式，能把对称的两两枚举变成单向的一次遍历，这是从 $O(n^2)$ 降到 $O(n)$ 最常用的视角转换。
  • 「同值只需保留最近一次出现」是一条可迁移的剪枝原则：当判据关于距离单调时，更早的候选被更晚的候选严格支配，可以安全丢弃。
  • 先查表后写表的顺序不是风格问题而是正确性问题，凡是「当前元素不能和自己配对」的题都必须把写操作放在查操作之后。
  • 面试视角：这题面试官真正在看的是你能否说清「为什么覆盖旧下标是安全的」。只写出五行代码而讲不出支配关系，会被追问到答不上来；能主动提出 k = 0 和「k 大于数组长度时退化为 217」这两个边界，则加分明显。另一个常被追问的等价写法是维护一个大小为 k 的滑动窗口集合，空间可降到 $O(\min(n, k))$，可以作为后续优化点主动提出。

易错点总结

  • 把 last.put(nums[i], i) 写在查询之前：用例 nums = [1, 2, 3], k = 1，第 0 位写入后立刻查到 prev = 0，0 - 0 = 0 <= 1 成立，返回 true，而正确答案是 false。
  • 用 Set 而不是 Map 只记「出现过」：用例 nums = [1, 2, 3, 1], k = 2，会因为看到重复的 1 就返回 true，但实际距离是 3，正确答案是 false。
  • 命中旧值但距离超限时选择 continue 而不覆盖记录：用例 nums = [1, 0, 1, 1], k = 1，表里的 1 一直停在下标 0，到 i = 3 算出距离 3，返回 false，而正确答案是 true。
  • 用 int prev = last.get(nums[i]) 而不先判空：用例 nums = [1, 2, 3], k = 1，第 0 位取到 null 后拆箱，抛出 NullPointerException。
  • 判断写成 i - prev < k：用例 nums = [1, 1], k = 1，1 - 0 = 1 不小于 1，返回 false，而正确答案是 true，题目给的是闭区间 <=。
  • 用 last.getOrDefault(nums[i], -1) 后直接比较 i - prev <= k：用例 nums = [5], k = 1 尚可，但 nums = [5, 6], k = 5 时 i = 0 取到 -1，0 - (-1) = 1 <= 5 成立，返回 true，而正确答案是 false；默认值必须选成不可能满足条件的极小值如 Integer.MIN_VALUE，且要防减法溢出。
  • 直接对 nums[i] 排序后找相邻相等元素：用例 nums = [1, 2, 3, 1], k = 3，排序打乱了下标，abs(i - j) 已无从计算，得到的答案与真实位置无关。
  • 用 nums[i] == nums[j] 的双重循环并把内层写成 for (int j = i + 1; j < nums.length; j++) 却不加 j - i > k 的提前跳出：用例长度 10^5 的全互异数组，会执行约 50 亿次比较而超时。
  • Go 里写成 if prev := last[v]; v != 0 && i-prev <= k，用值是否为零来判断存不存在：用例 nums = [0, 1, 0], k = 2，值 0 永远走不到判断分支，返回 false，而正确答案是 true；必须用 prev, ok := last[v] 的双返回值形式。

相似题目

题目 难度 考察点
217. 存在重复元素 简单 去掉了距离约束，只需集合判重，是本题在 k 无穷大时的退化形态
220. 存在重复元素 III 困难 值也放宽成相差不超过 t，哈希查不出来，需要有序结构或桶
1. 两数之和 简单 同样是先查后写的哈希配对，但配对条件是求和而非相等
3. 无重复字符的最长子串 中等 记录字符最近位置后用来推进左边界，从判存在升级为求最优长度
438. 找到字符串中所有字母异位词 中等 窗口大小固定但状态是整张计数表，考察进出窗口时的增量维护