219. 存在重复元素 II - 力扣（LeetCode） (leetcode-cn.com)

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

分析

此题目的为寻找k区间的nums数组的重复元素，
例如： nums = [1,2,3,1] k=3 nums[0] == nums[4] ---> true (0和4距离为3 && 小于等于k，则为true) 
nums = [1,2,3,1] k=2 nums[0] == nums[4] ---> false (0和4距离为3 && 但不小于等于k，则为false) 
这就类似设置一个大小为k的滑动窗口，在滑动窗口中寻找重复元素， 
如果直接计算则时间复杂度为O(n*min(n,k))空间复杂度为O(1)， 
所以优化一下，使用哈希表存储滑动窗口中的元素，此时时间复杂度为O(n)，空间复杂度为O(min(n,k))。

解题

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