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.
一刷
利用bucket, bucket中最大最小值的差范围在t+1之间，于是要寻找的值只可能出现在相同的bucket或相邻的bucket。
- 遍历数组中的元素，i表示index, 如果index>=k, 那么要把之前存在map中，index小于i-k的元素删除。
- Bucket，一个bucket中的两个元素的value差小于等于t
//[0, t], [t+1, 2t+1], [2t+2, 3t+2]
每次遍历一个元素，
- 如果该bucket index已经存在map的key中，return true;
- 如果bucket index-1已经存在map的key中, 且value与nums[i]的value绝对值的差小于w, return true;
- 如果bucket index+1已经存在map的key中, 且value与nums[i]的value绝对值的差小于w, return true;
public class Solution {
private long getID(long i, long w) {
//[0, t], [t+1, 2t+1], [2t+2, 3t+2]
return i < 0 ? (i + 1) / w - 1 : i / w;
}
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (t < 0) return false;
Map<Long, Long> d = new HashMap<>();
long w = (long)t + 1;
for (int i = 0; i < nums.length; ++i) {
long m = getID(nums[i], w);
if (d.containsKey(m))
return true;
if (d.containsKey(m - 1) && Math.abs(nums[i] - d.get(m - 1)) < w)
return true;
if (d.containsKey(m + 1) && Math.abs(nums[i] - d.get(m + 1)) < w)
return true;
d.put(m, (long)nums[i]);
if (i >= k) d.remove(getID(nums[i - k], w));
}
return false;
}
}
