LeetCode 219 - 存在重复元素 II

题目描述

给你一个整数数组 nums 和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，满足：

1. nums[i] == nums[j]
2. abs(i - j) <= k

解题思路

1. 滑动窗口 + 集合

使用大小为 k 的滑动窗口和集合来解决：

1. 维护一个最大长度为 k 的集合
2. 遍历数组，对于每个元素：
   • 如果当前元素在集合中已存在，返回 true
   • 将当前元素加入集合
   • 如果集合大小超过 k，移除最早加入的元素

2. 代码实现

def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
    num_set = set()
    for i in range(len(nums)):
        if nums[i] in num_set:
            return True
        num_set.add(nums[i])
        if len(num_set) > k:
            num_set.remove(nums[i - k])
    return False