存在重复元素 II 图解题解

这道题到底在问什么

输入

nums = [1,2,3,1]，k = 3

输出

true（下标 0 和 3 都是 1，距离 3 ≤ k）

最优解：一步一步想明白

1. 3口诀：一张表 last 记每个数字「最后一次出现的下标」。每到一个数，先查上次位置算距离，再用这次下标覆盖。先查后更新。下面逐格演示。
2. 4指针 i 走到下标 0，值是 1。去表里查 1 之前在哪：表里还没有它。
3. 51 是第一次出现，把它的下标 0 记进表里，继续往后扫。
4. 6指针 i 走到下标 1，值是 2。去表里查 2 之前在哪：表里还没有它。
5. 72 是第一次出现，把它的下标 1 记进表里，继续往后扫。
6. 8指针 i 走到下标 2，值是 3。去表里查 3 之前在哪：表里还没有它。
7. 93 是第一次出现，把它的下标 2 记进表里，继续往后扫。
8. 10指针 i 走到下标 3，值是 1。表里查到 1 上次在下标 0，这次距离是 3 − 0 = 3。
9. 11距离 3 超过了 k=2，这一对太远不算。把 1 的「最后下标」更新成 3，继续往后扫。
10. 12指针 i 走到下标 4，值是 4。去表里查 4 之前在哪：表里还没有它。
11. 134 是第一次出现，把它的下标 4 记进表里，继续往后扫。
12. 14指针 i 走到下标 5，值是 5。去表里查 5 之前在哪：表里还没有它。
13. 155 是第一次出现，把它的下标 5 记进表里，继续往后扫。
14. 16指针 i 走到下标 6，值是 6。去表里查 6 之前在哪：表里还没有它。
15. 176 是第一次出现，把它的下标 6 记进表里，继续往后扫。
16. 18指针 i 走到下标 7，值是 6。表里查到 6 上次在下标 6，这次距离是 7 − 6 = 1。
17. 19距离 1 不超过 k=2，下标 6 和 7 这两个 6 挨得够近，条件满足，直接返回 true。
18. 20找到了高亮的这一对相等数字，且距离不超过 k，所以答案是 true。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

def containsNearbyDuplicate(nums, k):
    last = {}                    # 值 -> 最后出现的下标
    for i, x in enumerate(nums):
        if x in last and i - last[x] <= k:
            return True          # 相等且距离够近
        last[x] = i              # 更新这个值的最新下标
    return False

bool containsNearbyDuplicate(vector<int>& nums, int k){
    unordered_map<int,int> last;
    for (int i = 0; i < nums.size(); i++) {
        int x = nums[i];
        if (last.count(x) && i - last[x] <= k) return true;
        last[x] = i;
    }
    return false;
}

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

复杂度

面试官可能追问