0219. Contains Duplicate II

https://leetcode.com/problems/contains-duplicate-ii

Description

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

Example 1:

**Input:** nums = [1,2,3,1], k = 3
**Output:** true

Example 2:

**Input:** nums = [1,0,1,1], k = 1
**Output:** true

Example 3:

**Input:** nums = [1,2,3,1,2,3], k = 2
**Output:** false

Constraints:

• 1 <= nums.length <= 105

• -109 <= nums[i] <= 109

• 0 <= k <= 105

ac1: just hash map

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> hash = new HashMap<Integer, Integer>();

        for (int i = 0; i < nums.length; i++) {
            if (hash.containsKey(nums[i]) && i - hash.get(nums[i]) <= k) {
                return true; 
            }
            hash.put(nums[i], i);
        }

        return false;
    }
}

ac2: sliding window

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {

        int l = 0, r = 0;
        HashSet<Integer> set = new HashSet<>();
        while (r < nums.length) {
            if (r - l > k) {
                set.remove(nums[l++]);
            }

            if (set.contains(nums[r])) {
                return true;
            } else {
                set.add(nums[r++]);
            }
        }

        return false;
    }
}