219. 存在重复元素 II
题目描述
输入整数数组 nums 和整数 k。
判断能否找到两个不同的下标 i 和 j，使得两处的值相等，并且两个下标之差的绝对值不超过 k，即 abs(i - j) <= k。
能找到返回 true，否则返回 false。
示例 1
输入：nums = [1,2,3,1], k = 3 输出：true
解释：下标 0 和 3 的值都是 1，距离 3 不超过 k。
示例 2
输入：nums = [1,0,1,1], k = 1 输出：true
解释：下标 2 和 3 的值都是 1，距离为 1。
示例 3
输入：nums = [1,2,3,1,2,3], k = 2 输出：false
解释：相等元素之间的距离都是 3，超过了 k = 2。
数据范围
1 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^90 <= k <= 10^5
解题思路：滑动窗口 + 哈希集合
只关心“距离不超过 k”的两个数，所以对于当前下标 i，只需要看它前面最近的 k 个数。用一个集合保存这 k 个数，形成一个固定长度的滑动窗口：i 超过 k 时先把掉出窗口的 nums[i-k-1] 删掉，再查 x 是否在集合里，最后把 x 加入。
为什么正确
检查 nums[i] 之前，集合恰好是 nums[max(0,i-k) .. i-1] 中的值；如果其中有重复，早就已经返回 true，所以集合里的值互不相同。
复杂度分析
时间 O(n)，额外空间 O(min(n, k))。
易错点
删除过期元素的条件是 i > k，删除的是 nums[i - k - 1]。写成 i >= k 会把距离恰好为 k 的那个数提前删掉，漏判。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
window = set()
for i, x in enumerate(nums):
if i > k:
window.remove(nums[i - k - 1])
if x in window:
return True
window.add(x)
return Falseclass Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> window = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
int x = nums[i];
if (i > k) {
window.remove(nums[i - k - 1]);
}
if (window.contains(x)) {
return true;
}
window.add(x);
}
return false;
}
}class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_set<int> window;
for (int i = 0; i < (int)nums.size(); i++) {
int x = nums[i];
if (i > k) {
window.erase(nums[i - k - 1]);
}
if (window.count(x)) {
return true;
}
window.insert(x);
}
return false;
}
};func containsNearbyDuplicate(nums []int, k int) bool {
window := map[int]bool{}
for i, x := range nums {
if i > k {
delete(window, nums[i-k-1])
}
if window[x] {
return true
}
window[x] = true
}
return false
}var containsNearbyDuplicate = function(nums, k) {
const window = new Set();
for (let i = 0; i < nums.length; i++) {
const x = nums[i];
if (i > k) {
window.delete(nums[i - k - 1]);
}
if (window.has(x)) {
return true;
}
window.add(x);
}
return false;
};function containsNearbyDuplicate(nums: number[], k: number): boolean {
const window = new Set<number>();
for (let i = 0; i < nums.length; i++) {
const x = nums[i];
if (i > k) {
window.delete(nums[i - k - 1]);
}
if (window.has(x)) {
return true;
}
window.add(x);
}
return false;
}其他解法
哈希表保存每个值最近的下标，用下标差判断距离；滑动窗口只保留最近 k 个元素，只要在窗口内找到就满足距离要求，把空间从 O(n) 降到 O(k)。
解法 2：哈希表记录最近下标 时间 O(n)，空间 O(n)
用哈希表记录每个值最近一次出现的下标。遍历到 nums[i] 时，如果这个值之前出现过且 i 减去上次下标不超过 k，就返回 true；否则把该值的下标更新为 i。只需要比较最近一次，因为更早的下标距离只会更远。
不需要维护窗口的删除操作，写法更直接。哈希表会保存所有不同的值，空间是 O(n) 而不是 O(k)。
from typing import List
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
last = {}
for i, x in enumerate(nums):
if x in last and i - last[x] <= k:
return True
last[x] = i
return Falseclass Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer, Integer> last = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
Integer j = last.get(nums[i]);
if (j != null && i - j <= k) return true;
last.put(nums[i], i);
}
return false;
}
}class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_map<int, int> last;
for (int i = 0; i < (int)nums.size(); i++) {
auto it = last.find(nums[i]);
if (it != last.end() && i - it->second <= k) return true;
last[nums[i]] = i;
}
return false;
}
};func containsNearbyDuplicate(nums []int, k int) bool {
last := map[int]int{}
for i, x := range nums {
if j, ok := last[x]; ok && i-j <= k {
return true
}
last[x] = i
}
return false
}var containsNearbyDuplicate = function(nums, k) {
const last = new Map();
for (let i = 0; i < nums.length; i++) {
if (last.has(nums[i]) && i - last.get(nums[i]) <= k) return true;
last.set(nums[i], i);
}
return false;
};function containsNearbyDuplicate(nums: number[], k: number): boolean {
const last = new Map<number, number>();
for (let i = 0; i < nums.length; i++) {
const j = last.get(nums[i]);
if (j !== undefined && i - j <= k) return true;
last.set(nums[i], i);
}
return false;
};