LeetCode 219. 存在重复元素 II

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

题目描述

✅ 219. 存在重复元素 II

image-20260928230953994

题意分析

判断是否存在值相等、下标距离不超过 k 的两个不同位置。

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

核心思路

[!blue]

扫描到下标 i 时，用哈希表 last 保存每个值此前最近一次出现的下标。若当前值上次出现在 prev，只需检查 i-prev <= k：任何更早的同值位置 j 都满足 j <= prev，所以 i-j >= i-prev。最近位置都太远时，更早位置也不可能合格。

必须先读取旧记录，再写入当前下标，保证配对的两个位置不同。若旧位置不存在或距离过大，也要把 last[nums[i]] 更新为 i，因为它会成为未来同值元素最近的候选。

若存在合法配对，扫描到其中较右的位置时，最近的同值位置只会更近，也必然满足限制。因此最近候选合格就立即返回 true，全部扫描完仍未找到才返回 false。当 k = 0 时，不同位置的距离至少为 1，所有比较都会失败，无需额外分支。

解题步骤

  • 按下标扫描，查询同值最近位置。
  • 存在且距离不超过限制时成功。
  • 否则仍更新到当前位置。
  • 遍历结束仍未找到合法配对，返回 false。

代码实现

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)$，n 为数组长度，每项一次哈希查找与更新。
  • 空间复杂度：$O(u)$，u 为不同值数量。

关键点总结

[!green]

  • 最近的同值位置距离最小，其他更早位置不会提供更好的候选。
  • 零下标是有效记录，存在性不能靠下标是否为零判断。

易错点总结

[!yellow]

  • 命中但超距就跳过更新，会漏掉之后更近的重复。
  • 当前下标先写再查，会与自己组成距离零。
  • 把不超过写成严格小于，会漏掉距离恰好为 k。

相似题目

题目 难度 关联与区别
217. 存在重复元素 简单 增加下标距离限制后，不能只记某值是否出现过，还需最近位置或窗口。
220. 存在重复元素 III 困难 原题进一步允许数值接近而不完全相等，需要有序结构或桶查询。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/43310375
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！