［抄题］：
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:
Input: nums = [1,2,3,1], k = 3, t = 0
Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1, t = 2
Output: true
Example 3:
Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false
[暴力解法]：
时间分析：
空间分析：
[优化后]：
时间分析：
空间分析：
［奇葩输出条件］：
［奇葩corner case］：
bucket值可能很小，所以用 让分子变大。
- Integer.MIN_VALUE［思维问题］：
以为2个指针，没想到果然有技巧
［英文数据结构或算法，为什么不用别的数据结构或算法］：
水桶排序的精髓在于容量恒定，重复出现的放在下一个水桶。此题要求数字差值恒定，所以可以用水桶排序。
做法：/容量即可。类似取余数。
［一句话思路］：
差值不超过t, 而且越近越好。在k范围内的bucket值重复出现肯定可以，相邻的检查一下也可以。
［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：
［画图］：
［一刷］：
- map里存的是对象，变量类型都是大写开头。只能用put方法。其他一般的变量类型用小写开头即可。
long remappedNum = (long) nums[i] - Integer.MIN_VALUE;每个变量都要改成long- 求map整个一坨的方法是：
if (map.keySet().size() > k)
［二刷］：
long型放在分母时，要加括号
/ ((long)t + 1);
［三刷］：
［四刷］：
［五刷］：
[五分钟肉眼debug的结果]：
nums[i - k] 要不要-1 自己试试就行了，也是debug的一个重点
［总结］：
水桶排序要求不能重复。做法：/容量即可。类似取余数。
［复杂度］：Time complexity: O(n) Space complexity: O(n)
［算法思想：迭代/递归/分治/贪心］：
［关键模板化代码］：
［其他解法］：
［Follow Up］：
［LC给出的题目变变变］：
[代码风格] ：
[是否头一次写此类driver funcion的代码] ：
[潜台词] ：
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
//cc
if (nums == null || nums.length == 0) return false;
if (k < 1 || t < 0) return false;
//ini: HashMap, bucket
HashMap<Long, Long> map = new HashMap<>();
//for loop: judge as true in 3 cases, add(bucket, value) to map while maintain k
for (int i = 0; i < nums.length; i++) {
long appendedNum = (long)nums[i] - Integer.MIN_VALUE;
long bucket = appendedNum / ((long)t + 1);
//judge as true in 3 cases
if (map.containsKey(bucket) ||
(map.containsKey(bucket - 1) && Math.abs(appendedNum - map.get(bucket - 1)) <= t) ||
(map.containsKey(bucket + 1) && Math.abs(map.get(bucket + 1) - appendedNum) <= t)) return true;
//while maintain k numbers in the map
if (map.entrySet().size() >= k) {
long lastBucket = ((long)nums[i - k] - Integer.MIN_VALUE) / ((long)t + 1);
map.remove(lastBucket);
}
//put to map
map.put(bucket, appendedNum);
}
return false;
}
}