219. Contains Duplicate II

Question

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

Solution

这道题和Contains Duplicate I思路一样，但是因为多了index的差的范围的限制，考虑sliding windows，即window每次向右移动一格，添加新遇到的元素，删除最左边的元素，这样就能保证index的差在一定范围内。其他和Contains Duplicate I一样。

代码如下：

public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums == null || nums.length <= 1) {
            return false;
        }

        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (i > k) {
                set.remove(nums[i - k - 1]);
            }
            if (!set.add(nums[i])) {
                return true;
            }
        }

        return false;
    }
}