leetcode 220 Contains Duplicate

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.

Example 1:

1 2	Input: nums = [1,2,3,1], k = 3, t = 0 Output: true

Example 2:

1 2	Input: nums = [1,0,1,1], k = 1, t = 2 Output: true

Example 3:

1 2	Input: nums = [1,5,9,1,5,9], k = 2, t = 3 Output: false

使用hashmap来保存t个数
将每个数模(t+1)，将其放入对应的bucket中，那么每个bucket中的number的index差可定是在0-t之间的。
对于相邻的两个bucket，也可能存在index差在0-t的number，一次，对于每个相邻的bucket，需要检查是否index差小于t
nums[i]可能是负数，若负数模(t+1)，对应的bucket会错位，因此，nums[i]需要将其全部转换为正数，即nums[i]-Integer.MIN_VALUE;
控制hashmap的item数目，来保证所求的index距离小于等于k
Corner case是k<1 || t < 0

class  大专栏  leetcode 220 Contains Duplicate - zerteenpan>{
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        HashMap<Long, Long> m = new HashMap<>();
        if ( k < 1 || t < 0) 
            return false;
        for (int i=0; i<nums.length; i++) {
            long mapped = (long)nums[i] - Integer.MIN_VALUE;
            long bucket = mapped/((long)t+1);
            if (m.containsKey(bucket)) {
                return true;
            }
            if (m.containsKey(bucket-1) && (mapped - m.get(bucket-1)) <= t) {
                return true;
            }
            if (m.containsKey(bucket+1) && (m.get(bucket+1) - mapped) <= t) {
                return true;
            }
            if (i >= k) {
                m.remove(((long)nums[i-k]-Integer.MIN_VALUE)/((long)t+1));
            }
            m.put(bucket, mapped);
        }
        return false;
    }
}