220. 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 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;
    }
}