Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.
Solution：Bucket
思路：
Bucket:
t = 3
nums = 3 4 5 6 7 8 9 10
"remaped / t" = 1 1 1 2 2 2 3 3
将nums中的元素归一化(主要是除以t) 后按归一化后的值存在桶里，同一个桶内的数组数值范围肯定是t；
基本思路，就是说每来一个元素，来一个桶("范围内t的")装着它，直到装到k个元素(保证要找的两个元素的index difference是<=k个的)。如果没有满足t条件时，每个桶中一个元素。
此时下一个元素如果是这些桶里的，或者是隔壁桶里满足 && map.get(bucket +- 1) - remappedNum <= t的，则return True; 若不是这个桶里的，则更新：来一个新桶("范围内t的")装着它，并删除nums[i - k]对应的桶来保证要找的两个元素的index difference是<=k个的，也就是只有k个桶。
Time Complexity: O(N) Space Complexity: O(N)
Solution Code：
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (k < 1 || t < 0) return false;
Map<Long, Long> map = new HashMap<>(); // bucket_num -> remappedNum
for (int i = 0; i < nums.length; i++) {
long remappedNum = (long) nums[i] - Integer.MIN_VALUE;
long bucket = remappedNum / ((long) t + 1); // + 1 to avoid zero
if (map.containsKey(bucket)
|| (map.containsKey(bucket - 1) && remappedNum - map.get(bucket - 1) <= t)
|| (map.containsKey(bucket + 1) && map.get(bucket + 1) - remappedNum <= t))
return true;
if (map.entrySet().size() >= k) {
long lastBucket = ((long) nums[i - k] - Integer.MIN_VALUE) / ((long) t + 1);
map.remove(lastBucket);
}
map.put(bucket, remappedNum);
}
return false;
}
}
