219. 存在重复元素 II

题目链接：219. 存在重复元素 II

题目描述

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

核心思考：定长滑动窗口与哈希表映射

这道题在刚做完一系列滑动窗口变种题后，很容易形成思维定势，想当然地去套用标准的常规“左右双指针动态滑动窗口”模板。这种解法确实可行，但对于这道题，我们其实有更为优雅且直指本质的解法。

我们可以把这道题您演进的两种解法进行一次层层递进的对比：

解法一：显式滑动窗口 (Set 维护)

这是最标准的双指针防越界姿势。我们通过维护一个最大跨度为 k 的窗口（利用 Set 集合来判断窗口内是否有重复元素），当 right 指针向右枚举时：

1. 若新元素已存在于 contain 集合中，说明在距离 k 的范围内找到了重复元素，立刻返回 True。
2. 若不在，则将其加入集合。
3. 当窗口跨度超标（right - left > k）时，说明最左侧的元素已经不再可用，将其从集合中剔除，并推进 left 指针将窗口收缩至合法长度。

解题思路 1 (Python)

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        # 很明显不能暴力
        # 窗口不能大于k
        l = len(nums)
        left = right = 0
        contain = set()
        while right < l:
            if nums[right] in contain:
                return True
            contain.add(nums[right])
            right += 1
            while right - left > k:
                contain.remove(nums[left])
                left += 1
        return False

反思： 正如您所洞察到的，在长度固定的窗口约束下，上述显式的 while 控制双指针确实有些“做傻了”。更优雅的做法是直接利用 enumerate() 来替代 right 指针的迭代，让代码更具 Pythonic 的简洁美。

解法二：哈希表精准打击（摒弃显式滑动）

如果我们跳出滑动窗口的思想，回归题目的本质：这道题无非是想考察，数组中相同数值的任意两个索引，其差值是否不超过 k。

既然如此，单次遍历搭配“哈希表”的直接记录才是这题真正的大杀器。我们放弃刻意维护那些被滑动窗口框住的元素集合，改为直接用一个字典（散列表）来全局记录每个元素最后一次出现的最新索引位置。

核心流转逻辑如下：

1. 单次遍历扫描到每个元素 num 和它当前的序号 i。
2. 检查这个 num 之前是否有历史记录？如果存在，计算当前坐标 i 与历史坐标 seen[num] 的差值。如果在 k 之内，直接胜利返回 True。
3. 如果没有满足距离要求，或者这是这个数第一次露脸，那没关系，我们直接用当前最新、最靠后的索引 i 去更新它在字典中的座标体系。因为对于未来可能出现的相同的数而言，它需要寻找的一定是那个离它最近（即索引越靠后）的重复数字，这种贪心更新策略是完美且最优的。

解题思路 2 (Python)

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        seen = {}
        for i, num in enumerate(nums):
            if num in seen and i - seen[num] <= k:
                return True
            seen[num] = i
        return False

复杂度分析

不论是滑动窗口还是哈希表映射机制，时间消耗殊途同归：

• 时间复杂度：$O(N)$，其中 $N$ 是数组的长度。无论是对 Set 的增删查验，还是对哈希字典的数据覆盖，均是在 $O(1)$ 时间内完成。总体算法仅进行一次常数级的一维扫描计算，保持在彻底的线性约束下。
• 空间复杂度：
  • 滑动窗口法：$O(\min(N, k))$，在最极端情况下集合将随窗口大小容纳最多 $k+1$ 个元素。
  • 哈希表法：$O(N)$，最坏状态下所有元素截然不同，哈希表将保存接近 $N$ 个唯一的索引键值对映射，空间上做到了高度可控的存储换效率。