219.存在重复元素II

题目：

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。

示例 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

方法

维护一个最多包含k个元素的哈希set，让它起到一个滑动窗口的作用

从头到尾遍历数组：

• 如果当前元素存在于set中，则说明在距当前元素k步的范围内存在重复元素，直接返回true
• 如果当前元素不在set中，则将其加入set，如果加入后set大小大于k，则移除当前set中最早进来的数字，保证其大小始终不大于k。

时间复杂度：O(n)
空间复杂度：O(K)

代码

public boolean containsNearbyDuplicate(int[] nums, int k) {
    HashSet<Integer> set = new HashSet<>();
    for(int i = 0; i < nums.length; i++){
        if(set.contains(nums[i]))
            return true;
        else{
            set.add(nums[i]);
            if(set.size() > k)
                set.remove(nums[i - k]);
        }
    }
    return false;
}