题目描述
LC题 - 219
给你一个整数数组 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: 暴力枚举
static public func containsNearbyDuplicate1(_ nums: [Int], _ k: Int) -> Bool {
let n = nums.count
for i in 0..<(n-1) {
var j = i+1
while j <= (i+k) && j<n {
if nums[j] == nums[i] {
return true
}
j += 1
}
}
return false
}
思路2:哈希表
使用哈希表记录每个元素的最大下标。从左到右遍历数组nums，当遍历到下标i时，进行如下操作：
- 如果哈希表中已经存在和nums[i] 相等的元素且该元素在哈希表中记录的下标j满足i−j≤k，返回true；
- 将nums[i] 和下标i存入哈希表，此时i是nums[i] 的最大下标。
上述两步操作的顺序不能改变，因为当遍历到下标i 时，只能在下标i之前的元素中寻找与当前元素相等的元素及该元素的最大下标。
当遍历结束时，如果没有遇到两个相等元素的下标差的绝对值不超过k，返回false。
static public func containsNearbyDuplicate2(_ nums: [Int], _ k: Int) -> Bool {
let n = nums.count
var hash = [Int:Int]()
for i in 0..<n {
if hash.keys.contains(nums[i]) {
if i-hash[nums[i]]! <= k {
return true
}
}
hash[nums[i]] = i
}
return false
}
思路3: 滑动窗口
考虑数组nums中的每个长度不超过k+1 的滑动窗口，同一个滑动窗口中的任意两个下标差的绝对值不超过k。
如果存在一个滑动窗口，其中有重复元素，则存在两个不同的下标i和j满足nums[i]=nums[j] 且∣i−j∣≤k。如果所有滑动窗口中都没有重复元素，则不存在符合要求的下标。因此，只要遍历每个滑动窗口，判断滑动窗口中是否有重复元素即可。
如果一个滑动窗口的结束下标是i，则该滑动窗口的开始下标是max(0,i−k)。可以使用哈希集合存储滑动窗口中的元素。从左到右遍历数组nums，当遍历到下标i时，具体操作如下：
- 如果i>k，则下标i−k−1 处的元素被移出滑动窗口，因此将nums[i−k−1] 从哈希集合中删除；
- 判断nums[i] 是否在哈希集合中，如果在哈希集合中则在同一个滑动窗口中有重复元素，返回true，如果不在哈希集合中则将其加入哈希集合。
当遍历结束时，如果所有滑动窗口中都没有重复元素，返回false。
static public func containsNearbyDuplicate3(_ nums: [Int], _ k: Int) -> Bool {
let n = nums.count
var hash = [Int]()
for i in 0..<n {
if i > k {
hash.remove(at: 0)
}
if hash.contains(nums[i]) {
return true
}
hash.append(nums[i])
}
return false
}
参考：https://leetcode-cn.com/problems/contains-duplicate-ii
https://leetcode-cn.com/problems/contains-duplicate-ii/solution/cun-zai-zhong-fu-yuan-su-ii-by-leetcode-kluvk/
