如何用Python高效检测数组中指定距离内的重复元素？

核心思路 #

用滑动窗口+哈希集合就能实现O(n)时间复杂度的最优解，完全适配10^5级别的数组规模：

• 维护一个长度不超过k的窗口，用集合存储窗口内的所有元素，快速判断当前元素是否在最近k个元素中出现过
• 遍历数组时，每一步先检查当前元素是否在集合中：存在则直接返回True
• 若不存在，将当前元素加入集合；当窗口长度超过k时（即当前索引i >= k），移除窗口最左侧的元素（保证窗口始终只包含最近k个元素）
• 遍历结束后未找到符合条件的重复元素，返回False

Python 实现代码 #

def contains_nearby_duplicate(nums, k):
    window = set()
    for i, num in enumerate(nums):
        if num in window:
            return True
        window.add(num)
        # 窗口大小超过k时，移除最左侧元素
        if i >= k:
            window.remove(nums[i - k])
    return False

复杂度分析 #

• 时间复杂度：O(n)，每个元素最多被添加到集合和从集合移除各一次，集合的增删查操作都是O(1)平均时间
• 空间复杂度：O(k)，集合最多存储k个元素，远低于10^5的内存限制

示例验证 #

• 输入nums=[1,2,3,1], k=3：遍历到第4个元素1时，集合内是{1,2,3}，检测到重复，返回True
• 输入nums=[1,2,3,1], k=2：遍历到第4个元素1时，集合内是{2,3}（已移除最早的1），未检测到重复，最终返回False

额外说明 #

如果遇到k=0的边界情况（题目约束k小于数组长度，但未明确k≥1），此时只有同一索引的元素才算重复，直接返回False即可，代码中可以在开头加一行if k == 0: return False处理。

内容的提问来源于stack exchange，提问作者Pranav