LeetCode 219 - Contains Duplicate II
LeetCode 217 - Contains Duplicate
LeetCode 220 - Contains Duplicate III
http://www.programcreek.com/2014/05/leetcode-contains-duplicate-ii-java/
LeetCode 217 - Contains Duplicate
LeetCode 220 - Contains Duplicate III
http://www.programcreek.com/2014/05/leetcode-contains-duplicate-ii-java/
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.
X. Using Set and sliding window
public boolean containsNearbyDuplicate(int[] nums, int k) {
HashSet<Integer> hs=new HashSet<>();
for(int i=0;i<nums.length;i++)
{
if(hs.add(nums[i])==false) return true;
if(hs.size()==k+1) hs.remove(nums[i-k]);
}
return false;
}
My set only contain the numbers in the window. slide the window which is size k, if the new coming number cannot be add to set then return true. The time complexity is O(n), space complexity is O(k).
public boolean containsNearbyDuplicate(int[] nums, int k) {
HashSet<Integer> set = new HashSet<Integer>();
for(int i=0;i<nums.length && i<=k;i++){
if(!set.add(nums[i])){
return true;
}
}
for(int i=k+1;i<nums.length;i++){
set.remove(nums[i-k-1]);
if(!set.add(nums[i])){
return true;
}
}
return false;
}
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> set = new HashSet<Integer>();
for(int i = 0; i < nums.length; i++){
if(i > k) set.remove(nums[i-k-1]);
if(!set.add(nums[i])) return true;
}
return false;
}
http://my.oschina.net/Tsybius2014/blog/517511 public boolean containsNearbyDuplicate(int[] nums, int k) { if (nums.length <= 1) { return false; } HashSet<Integer> hashSet = new HashSet<Integer>(); for (int i = 0; i < nums.length; i++) { if (i > k) { hashSet.remove(nums[i - k - 1]); } if (!hashSet.add(nums[i])) { return true; } } return false; }
X. Using HashMap
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])){ int pre = map.get(nums[i]); if(i-pre<=k) return true; } map.put(nums[i], i); } return false; } |
Generally people forget that map.put() can return
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i < nums.length; i++) {
Integer ord = map.put(nums[i], i);
if(ord != null && i - ord <= k) {
return true;
}
}
return false;
}
def containsNearbyDuplicate(self, nums, k):
numDict = dict()
for x in range(len(nums)):
idx = numDict.get(nums[x])
if idx >= 0 and x - idx <= k:
return True
numDict[nums[x]] = x
return False
public boolean containsNearbyDuplicate(int[] nums, int k) { HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); int min = Integer.MAX_VALUE; for(int i=0; i<nums.length; i++){ if(map.containsKey(nums[i])){ int preIndex = map.get(nums[i]); int gap = i-preIndex; min = Math.min(min, gap); } map.put(nums[i], i); } if(min <= k){ return true; }else{ return false; } } |
Brute Force
public boolean containsNearbyDuplicate(int[] nums, int k) { if (nums.length <= 1) { return false; } for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j <= i + k && j < nums.length; j++) { if (nums[i] == nums[j]) { return true; } } } return false; }