题目链接
思路一：滑动窗口+红黑树查找
分析：这个题目意思简化一下就是两句话。
第一：元素之差 小于等于 t
第二：下标之差 小于等于 k
那么这里提到了下标的距离，那么很容易想到这里可以用到滑动窗口，而且这个窗口的大小是k。
这里t是大于等于0的，也就是说 nums[i]要满足第一个条件，必须存在 在 nums[i]-t到nums[i]+t范围内存在数字在窗口中。那么i从头遍历nums即可。
但是这里有个问题，这么去判断窗口中有没有在范围nums[i]-t和nums[i]+1内的数字存在呢？如果我们遍历窗口去判断，当然想法可以，但是窗口的大小，也就是k最大可以到104 ,因为我们还要遍历nums数组，数组长度最大2* 104,那么总的时间复杂度肯定超时了。
首先，我们可以想到，可以先将窗口中的数字进行排序，这样就可以方便后面进行加速查询效率。
其次，我们只需要在窗口中查询出来大于等于nums[i]-t的最小的元素。然后再看是否符合小于等于nums[i]+t即可。
那么这里我用到了数据结构TreeSet,它底层的实现是红黑树。并且提供了一个方法ceiling方法，正好可以返回树中大于等于某个元素的最小值。如果没有这样的元素存在，那么就返回null。
下面是代码实现：
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
//下标之差 小于等于 k
//元素之差 小于等于 t
if(k==0){
return false;
}
TreeSet<Long> set = new TreeSet<>();
for(int i=0; i<nums.length; i++){
//返回大于等于 nums[i]-t 的最小值 因为t一定是大于0的，所以nums[i]-t < nums[i]+t
Long ceiling = set.ceiling((long) nums[i] - (long)t);
if(ceiling!=null && ceiling<=(long)nums[i]+(long)t){
return true;
}
//窗口大小如果已经最大了，那么移除最前面的元素
if(set.size()==k){
//将第i-k个元素移除
set.remove((long)nums[i-k]);
}
//将当前元素加入窗口。
set.add((long) nums[i]);
}
return false;
}
}
思路二：桶排序
这个思路很巧妙。
分析：上面的查找窗口中是否存在在[ nums[i]-t , nums[i]+t ]范围内的元素，时间复杂度我们利用红黑树优化到了logn。
这里如果我们能将不同的数字放到不同的桶中，那么就可以做到实现O(1)复杂度了。
这里我们将桶的大小设置为（t+1），因为对于一个元素x，对于x,x+1,x+2,x+t都属于一个桶才对。所以桶的大小应该是t+1。
那么对于一个元素x 可以分为 x=(t+1)*a+b,
这个a就表示x放在标号为a的桶中。
那么对于当前元素，首先计算目标桶：
如果已经存在该桶，说明前面已有 [u - t, u + t][u−t,u+t] 范围的数字，返回 true
如果不存在该桶，则检查相邻两个桶的元素是有 [u - t, u + t][u−t,u+t] 范围的数字，如有 返回 true
这里有个要注意的地方
第一：对t进行+1操作
也就是容量为什么不是t而是t+1，举例假设t=3，对于0，1，2，3，如果不对t进行+1操作，那么0，1，2和3会在不同的桶中，所以才要对t进行+1。
也就是说连续两个差值为t的数，在数轴上的举例为t+1。
第二：负数为什么要+1
由于我们处理正数得时候，处理了数值0，所以负数这边从-1开始。
假设t=3，窗口得容量就是4，那么，-1，-2，-3，-4应该在一个桶中，如果直接用nums[i]/cap，那么-4就不会和其他三个在一个桶中，这个问题出现得根本原因是我们将0已经划到正数那边处理掉了。
第三：负数为什么最后还要减1
因为0号桶已经被用掉了，负数这边也会出现一个0号桶，所以才在基础上-1。
代码：
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
//x = (t+1)*a+b，，，， t+1是桶的大小 那么也就是说x在第a个桶中
//map中 key是桶的标号， val是值
Map<Long, Long> map = new HashMap<>();
long capcity = (long)t+1;
for(int i = 0; i<nums.length; i++){
long index = getIndexForTable(nums[i], capcity);
if(map.containsKey(index)){
//说明这个桶中已经有元素了，说明有两个元素的差距小于等于t
return true;
}
//隔壁桶有元素，并且隔壁桶中的元素和当前元素差距小于
if(map.containsKey(index-1) && Math.abs(map.get(index-1)-nums[i])<=t){
return true;
}
//隔壁桶有元素，并且隔壁桶中的元素和当前元素差距小于
if(map.containsKey(index+1) && Math.abs(map.get(index+1)-nums[i])<=t){
return true;
}
map.put(index,(long)nums[i]);
if(i>=k){
map.remove(getIndexForTable(nums[i-k],capcity));
}
}
return false;
}
/***
* 获取x所在的桶的位置
* @param x
* @param cap
* @return
*/
public long getIndexForTable(long x, long cap){
//当x为 [0,9]的时候，cap是10的时候，那么应该在此时[0,9]的数字都会在一个桶中
if(x>=0){
return x/cap;
}
//当x为[-1,-10]的时候，cap是10的时候，如果不+1，那么将不会在一个桶中，并且不能为0号桶，因为0号桶中放了 [0,9]的元素，所以应该是-1，从-1号桶开始
return (x+1)/cap -1;
}
}
疫情希望所有人顺利度过。