219. Contains Duplicate II - Easy

前往題目

想法

• Sliding window

思路

1. 走訪nums
2. 使用sliding window，用hashset記錄數字
3. 當window大於k，移除左指針數值，並且移動左指針
4. 如果找到重複的數字，就回傳true

Code

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        int l = 0;
        Set<Integer> window = new HashSet<>();

        for (int r = 0; r < nums.length; ++r) {
            // The window size is too large
            if (r - l > k) {
                window.remove(nums[l]); // Remove the leftmost element
                ++l; // move left pointer
            }

            // Found duplicate
            if (window.contains(nums[r])) {
                return true;
            }
            window.add(nums[r]);
        }
        return false;
    }
}