O(n) in Java using bucket

• The bucket idea comes from https://discuss.leetcode.com/topic/15199/ac-o-n-solution-in-java-using-buckets-with-explanation.
Basically, just use bucket = nums[i]/t as key of the hashmap to solve Contains Duplicate II.
So you only need to check bucket, bucket - 1, bucket + 1 for possible number in range t of current number.

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

}
return false;
}
``````

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.