[LeetCode] Contains Duplicate II

Contains Duplicate II

Given an array of integers and an integer k, return true if and only if 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: HashMap.
In the hash map, we use nums[i] as key, and the index i as value. 
If nums[j] = nums[i] (j > i), we check whether j - i <= k. If so, we return true. 
We update the value for the key nums[j] = nums[i] when j - i > k, or simply register the new pair (nums[j], j) when there does not exist an index i such that nums[j] = nums[i], where j > i.
Correctness: 
The observation is that if there exist indices a < b < c such that nums[a] = nums[b] = nums[c], then we only need to check whether b - a <= k, and c - b <= k, since c - a = (c - b) + (b - a). That being said, we only need to check two consecutive duplicate elements. This is what the hash map is doing, hence the algorithm is correct.

1 2 3 4 5 6 7 8 9 10 11 12 13 14

public class Solution { public boolean containsNearbyDuplicate(int[] nums, int k) { HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int i = 0; i < nums.length; i++) { if (map.containsKey(nums[i])) { if (i - map.get(nums[i]) <= k) { return true; } } map.put(nums[i], i); } return false; } }