LC219. 存在重复元素II

题目描述

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。 示例 1： 输入：nums = [1,2,3,1], k = 3 输出：true 示例 2： 输入：nums = [1,0,1,1], k = 1 输出：true 示例 3： 输入：nums = [1,2,3,1,2,3], k = 2 输出：false 提示： 1 <= nums.length <= 10^5 -109 <= nums[i] <= 10^9 0 <= k <= 10^5

题目解析

好的，没问题。我是 AlgoMooc 的算法老师，咱们今天就来把这道题彻底搞懂，保证零基础也能听得明明白白。

---

题目在说什么

这道题其实是在玩一个“找相同邻居”的游戏。

想象一下，你有一排数字卡片，每张卡片上写着一个数字。题目给了你两个条件： 1. 你要找到两张数字相同的卡片。 2. 这两张卡片的位置（索引）不能离得太远，它们之间的距离（也就是索引差的绝对值）必须小于或等于一个给定的数字 k。

如果找到了，就返回 true（表示“找到了”）；如果翻遍了所有卡片都没找到，就返回 false（表示“没找到”）。

举个例子： 卡片是 [1, 2, 3, 1]，k = 3。

• 第一张卡片是 1，位置是 0。
• 第二张卡片是 2，位置是 1。
• 第三张卡片是 3，位置是 2。
• 第四张卡片是 1，位置是 3。

你看，第一张和第四张卡片上的数字都是 1，它们的位置分别是 0 和 3。它们之间的距离是 |0 - 3| = 3，刚好等于 k。所以，符合条件！返回 true。

再比如 [1, 2, 3, 1, 2, 3]，k = 2。

• 数字 1 出现在位置 0 和 3，距离是 3，大于 2。
• 数字 2 出现在位置 1 和 4，距离是 3，大于 2。
• 数字 3 出现在位置 2 和 5，距离是 3，大于 2。

没有一个符合距离 <= 2 的条件，所以返回 false。

---

思路是怎么来的

新手朋友可能会想：“这还不简单？我拿两个for循环，把每一对卡片都检查一遍不就行了？” 比如，检查 (0,1)，(0,2)，(0,3)... 这样确实可以，但是效率太低了。如果有一万张卡片，就要检查将近五千万次，电脑会累坏的。

那有没有更聪明的方法呢？有的。我们换个思路。

想象一下，你是一个图书管理员，正在整理一排书架上的书。你的任务是：找出有没有两本完全相同的书，并且它们之间的距离不超过 `k` 个位置。

你会怎么做呢？你肯定不会傻傻地来回跑着对比每一对书。

你会这样做： 1. 你从左边第一本书开始，一本一本地看。 2. 同时，你手里拿着一张便利贴。每当你看到一本新书，你就把这本书的名字和它所在的位置记在便利贴上。 3. 当你看到下一本书时，你首先会看看便利贴上有没有记过这本书的名字。

• 如果有：说明你之前见过这本书。你马上看看便利贴上记的上次位置和现在的位置，算算距离是不是 <= k。如果是，恭喜你，找到了！
• 如果没有：说明这是本新书，你就把它的名字和当前位置记在便利贴上。

4. 你继续往前走，重复第3步。如果走到最后都没找到，那就说明没有这样的两本书。

这个“便利贴”就是计算机里的哈希表（也叫字典，Map）。它最大的本事就是能让你瞬间知道一个东西（比如书名）是不是在里面，并且能立刻取出它对应的信息（比如上次的位置）。

为什么这个思路好？ 因为我们只遍历了一次书架（数组），每本书只看一次，而且查便利贴的速度飞快。这就把原来需要“两两对比”的笨办法，变成了“边走边记，随时查询”的聪明办法。

---

代码逐步拆解

我们来看参考代码，一行一行地拆解。

public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {

        // 1. 准备一个“便利贴”（哈希表）
        // 这个 map 的作用是：记录每个数字“最近一次”出现的位置。
        // 键（Key）是数字本身，值（Value）是它出现的位置（索引）。
        Map<Integer, Integer> pos = new HashMap<>();

        // 2. 开始遍历书架（数组）
        // i 是当前位置（索引），v 是当前位置上的数字（元素值）
        for (int i = 0; i < nums.length; i++) {
            int v = nums[i];
            
            // 3. 核心判断：检查便利贴上有没有这个数字 v
            // pos.containsKey(v) 就是在问：“我见过数字 v 吗？”
            // 如果见过，并且 当前位置 i 减去 上次位置 pos.get(v) 的距离 <= k
            if (pos.containsKey(v) && i - pos.get(v) <= k) {
                // 如果两个条件都满足，那就找到啦！返回 true
                return true;
            }
            // 4. 更新便利贴
            // 不管有没有找到，我们都要把当前这个数字 v 的位置 i 更新到便利贴上。
            // 为什么？因为如果以后又出现一个相同的数字 v，我们需要用“最近一次”的位置来判断距离。
            // 所以，要把旧的位置覆盖掉，换成最新的位置 i。