Contains Duplicate I
Given an array of integers, find if the array contains any duplicates.
Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
Example 1:
Input: [1,2,3,1]
Output: true
Example 2:
Input: [1,2,3,4]
Output: false
Example 3:
Input: [1,1,1,3,3,4,3,2,4,2]
Output: true
public boolean containsDuplicate(int[] nums) {
Set<Integer> distinct = new HashSet<>();
for(int num : nums) {
if(distinct.contains(num)) {
return true;
}
distinct.add(num);
}
return false;
}
Contains Duplicate III
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] andnums[j] is at most t and the difference between i and j is at most k.
public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if(nums==null||nums.length<||k<||t<)
return false;
TreeSet<Long> set = new TreeSet<Long>();
for(int i=; i<nums.length; i++){
long curr = (long) nums[i];
long leftBoundary = (long) curr-t;
long rightBoundary = (long) curr+t+; //right boundary is exclusive, so +1
SortedSet<Long> sub = set.subSet(leftBoundary, rightBoundary);
if(sub.size()>)
return true;
set.add(curr);
if(i>=k){ // or if(set.size()>=k+1)
set.remove((long)nums[i-k]);
}
}
return false;
}
}