网络异常，图片无法展示
|
题目描述
这是 LeetCode 上的 219. 存在重复元素 II ，难度为 简单。
Tag : 「滑动窗口」、「哈希表」
给你一个整数数组 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 <= nums.length <= 10^51<=nums.length<=105
- -10^9 <= nums[i] <= 10^9−109<=nums[i]<=109
- 0 <= k <= 10^50<=k<=105
滑动窗口 + 哈希表
整理题意：是否存在长度不超过的 k + 1k+1 窗口，窗口内有相同元素。
我们可以从前往后遍历 numsnums，同时使用 Set 记录遍历当前滑窗内出现过的元素。
假设当前遍历的元素为 nums[i]nums[i]：
- 下标小于等于 kk（起始滑窗长度还不足 k + 1k+1）：直接往滑窗加数，即将当前元素加入
Set中； - 下标大于 kk：将上一滑窗的左端点元素 nums[i - k - 1]nums[i−k−1] 移除，判断当前滑窗的右端点元素 nums[i]nums[i] 是否存在
Set中，若存在，返回True，否则将当前元素 nums[i]nums[i] 加入Set中。
重复上述过程，若整个 numsnums 处理完后仍未找到，返回 False。
代码（感谢 @Benhao 同学提供的其他语言版本）：
class Solution { public boolean containsNearbyDuplicate(int[] nums, int k) { int n = nums.length; Set<Integer> set = new HashSet<>(); for (int i = 0; i < n; i++) { if (i > k) set.remove(nums[i - k - 1]); if (set.contains(nums[i])) return true; set.add(nums[i]); } return false; } } 复制代码
class Solution: def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool: n = len(nums) s = set() for i in range(n): if i > k: s.remove(nums[i - k - 1]) if nums[i] in s: return True s.add(nums[i]) return False 复制代码
func containsNearbyDuplicate(nums []int, k int) bool { n := len(nums) set := map[int]bool{} for i := 0; i < n; i++ { if i > k { set[nums[i - k - 1]] = false } if set[nums[i]] { return true } set[nums[i]] = true } return false } 复制代码
- 时间复杂度：O(n)O(n)
- 空间复杂度：O(k)O(k)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.219 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
