BiruLyu
7/13/2017 - 1:37 AM

## 220. Contains Duplicate III(#).java

``````public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if(t<0 || k<=0) return false;
if(nums==null || nums.length<2) return false;
HashMap<Long,Integer> map=new HashMap<Long,Integer>();
for(int i=0;i<nums.length;i++){
long bucket=((long)nums[i]-(long)Integer.MIN_VALUE)/((long)t+1);
if(map.containsKey(bucket) || (map.containsKey(bucket+1) && ((long)map.get(bucket+1)-(long)nums[i])<=((long)t) ) ||
(map.containsKey(bucket-1) && ((long)nums[i]-(long)map.get(bucket-1))<=((long)t))) return true;
if(i-k>=0){
long removedBucket=((long)nums[i-k]-(long)Integer.MIN_VALUE)/((long)(t+1));
map.remove(removedBucket);
}
map.put(bucket,nums[i]);
}

return false;

}
}``````
``````public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (nums == null || nums.length < 1 || k <= 0) return false;
int len = nums.length;
TreeSet<Long> tree = new TreeSet<>();
for (int i = 0; i < len; i++) {

final Long ceil = tree.ceiling((long)nums[i] - t);
final Long floor = tree.floor((long)nums[i] + t);
if ((ceil != null && ceil <= nums[i] ) || (floor != null && floor >= nums[i])) {
return true;
}
//if (tree.size() == k) { WA [1] 1 1
if (i >= k) {
tree.remove((long)nums[i - k]);
}
}
return false;
}
}

/*
[-2147483648,-2147483647]
3
3
*/``````