题目

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

示例 1：

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

示例 2：

• 输入：nums = [1,0,1,1], k = 1
• 输出：true

示例 3：

• 输入：nums = [1,2,3,1,2,3], k = 2
• 输出：false

方法一：哈希表

思路及解法

从左到右遍历数组 ，当遍历到下标 时，如果存在下标 使得 ，则当 时即找到了两个符合要求的下标 和 。

如果在下标 之前存在多个元素都和 相等，为了判断是否存在满足 且 的下标 ，应该在这些元素中寻找下标最大的元素，将最大下标记为 ，判断 是否成立。

如果 ，则找到了两个符合要求的下标 和 ；如果 ，则在下标 之前不存在任何元素满足与 相等且下标差的绝对值不超过 ，理由如下。

假设存在下标 满足 且 ，则 ，由于 ，因此必有 。

因此，当遍历到下标 时，如果在下标 之前存在与 相等的元素，应该在这些元素中寻找最大的下标 ，判断 是否成立。

可以使用哈希表记录每个元素的最大下标。从左到右遍历数组 ，当遍历到下标 时，进行如下操作：

1. 如果哈希表中已经存在和 相等的元素且该元素在哈希表中记录的下标 满足 ，返回 ；

2. 将 和下标 存入哈希表，此时 是 的最大下标。

上述两步操作的顺序不能改变，因为当遍历到下标 时，只能在下标 之前的元素中寻找与当前元素相等的元素及该元素的最大下标。

当遍历结束时，如果没有遇到两个相等元素的下标差的绝对值不超过 ，返回 。

代码

class Solution {
    func containsNearbyDuplicate(_ nums: [Int], _ k: Int) -> Bool {
        var map: [Int:Int] = [:]
        for i in 0..<nums.count {
            let num = nums[i]
            if nil != map[num] && (i - (map[num] ?? 0)) <= k {
                return true
            }
            map[num] = i
        }
        return false
    }
}

复杂度分析

• 时间复杂度：，其中 是数组 的长度。需要遍历数组一次，对于每个元素，哈希表的操作时间都是 。

• 空间复杂度：，其中 是数组 的长度。需要使用哈希表记录每个元素的最大下标，哈希表中的元素个数不会超过 。

方法二：滑动窗口

思路及解法

考虑数组 nums 中的每个长度不超过 k + 1 的滑动窗口，同一个滑动窗口中的任意两个下标差的绝对值不超过 k。如果存在一个滑动窗口，其中有重复元素，则存在两个不同的下标 i 和 j 满足 nums[i]=nums[j] 且 ∣i−j∣≤k。如果所有滑动窗口中都没有重复元素，则不存在符合要求的下标。因此，只要遍历每个滑动窗口，判断滑动窗口中是否有重复元素即可。

如果一个滑动窗口的结束下标是 i，则该滑动窗口的开始下标是 max(0,i−k)。可以使用哈希集合存储滑动窗口中的元素。从左到右遍历数组 nums，当遍历到下标 i 时，具体操作如下：

1. 如果 i>k，则下标 i−k−1 处的元素被移出滑动窗口，因此将 nums[i−k−1] 从哈希集合中删除；
2. 判断 nums[i] 是否在哈希集合中，如果在哈希集合中则在同一个滑动窗口中有重复元素，返回 true，如果不在哈希集合中则将其加入哈希集合。

当遍历结束时，如果所有滑动窗口中都没有重复元素，返回 false。

代码

class Solution {
    func containsNearbyDuplicate(_ nums: [Int], _ k: Int) -> Bool {
        var set = Set<Int>()
        for i in 0..<nums.count {
            if i > k {
                set.remove(nums[i - k - 1])
            }
            if set.contains(nums[i]) {
                return true
            }
            set.insert(nums[i])
        }
        return false
    }
}

复杂度分析

• 时间复杂度：，其中 是数组 的长度。需要遍历数组一次，对于每个元素，哈希集合的操作时间都是 。

• 空间复杂度：，其中 是判断重复元素时允许的下标差的绝对值的最大值。需要使用哈希集合存储滑动窗口中的元素，任意时刻滑动窗口中的元素个数最多为 个。