Created
July 8, 2016 15:19
-
-
Save qingl97/9002dead19f01bb3ddf390e27805311e to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Contains_Nearby_Dumplicate { | |
public boolean containsNearbyDuplicate(int[] nums, int k) { | |
// idea is to maintain a set of size k that obsorbing elements in the array | |
// from the head. From the k+1 th element, remove the i-k-1 th element that | |
// was previously added from the set then check if the newly added element is | |
// contained in the set by calling set.add() who return false if an element of | |
// the same value already exists. | |
Set<Integer> window = new HashSet<Integer>(); | |
for(int i=0; i<nums.length; i++) { | |
if(i > k) window.remove(nums[i-k-1]); | |
if(!window.add(nums[i])) return true; | |
} | |
return false; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment