219. Contains Duplicate II

二刷
Versuib #2 Sliding Window
14.63 %
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums == null) {
            return false;
        }
        // sliding window of size k
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.size() > k) {
                set.remove(nums[i - k - 1]);
            }
            if (set.contains(nums[i])) {
                return true;
            }
            set.add(nums[i]);
        }
        return false;
    }
}

Version #1 第一反应还是写了hashmap
Seems like this problem is actually a sliding window problem
81.40 %
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        // key-> num, value -> index
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            Integer index = map.get(nums[i]);
            if (index != null && i - index <= k) {
                return true;
            }
            map.put(nums[i], i);
        }
        return false;
    }
}


一刷
Version #2 HashSet(Better)
82.57 %
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums == null || nums.length <= 1) return false;
        // set of numbers in the sliding window
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            // i - j <= k ->  j >= i - k
            if (i - k > 0) {
                set.remove(nums[i - k - 1]);
            }
            if (!set.add(nums[i])) return true;
        }
        return false;
    }
}

Version #1 HashMap
看了答案发现自己这么写很烂
这个题有点像sliding window
只要用set看window里面有没有重复值就可以了

9.84 %
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums == null || nums.length <= 1) return false;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int prev = map.getOrDefault(nums[i], -1);
            if (prev != -1 && i - prev <= k) {
                return true;
            } else {
                map.put(nums[i], i);
            }
        }
        return false;
    }
}