存在重复元素2

发表于 分类于 阅读次数：

存在重复元素2（难度：简单）

1

方法：哈希表

维护一个哈希表，里面始终最多包含 k 个元素，当出现重复值时则说明在 k 距离内存在重复元素。 每次遍历一个元素则将其加入哈希表中，如果哈希表的大小大于 k，则移除最前面的数字。

复杂度

时间复杂度：O(n)。我们会做 n 次 搜索，删除，插入操作，每次操作都耗费常数时间。

空间复杂度：O(min(n,k))。开辟的额外空间取决于散列表中存储的元素的个数，也就是滑动窗口的大小。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> res = new HashSet<>();
        for(int i = 0; i < nums.length; i++){
            if(res.contains(nums[i]))
                return true; // 因为res的大小维持为k
            res.add(nums[i]);
            if(res.size()>k)
                res.remove(nums[i-k]);   
        }
        return false;
    }
}
2