题目描述

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

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

解题思路

1. 滑动窗口 + 集合

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

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

2. 代码实现

1
2
3
4
5
6
7
8
9
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

相关题目：LeetCode 217 - 存在重复元素

给你一个整数数组 nums。如果任一值在数组中出现至少两次，返回 true；如果数组中每个元素互不相同，返回 false。

示例 1

输入：nums = [1,2,3,1]
输出：true
解释：元素 1 在下标 0 和 3 出现。

示例 2

输入：nums = [1,2,3,4]
输出：false
解释：所有元素都不同。

示例 3

输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true

提示

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
1
2
def containsDuplicate(self, nums: List[int]) -> bool:
    return len(nums) != len(set(nums))