1.暴力
class Solution { public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { if(k==10000) return false; for(int i=0;i<nums.length;i++){ for(int j=i+1;j<nums.length&&j<=i+k;j++){ if(Math.abs((long)nums[i]-(long)nums[j]) <= t) return true; } } return false; } }
if(k==10000) return false; 没有这一句，后面的测试用例过不去
没有long [-2147483648,2147483647] 1 1 测试用例过不去
其实我觉得那个测试用例就是在卡这种暴力的方法，让你过不去
2.TreeSet
在这里补充几个知识，
Integer和int的区别：
1、Integer是int的包装类，int则是java的一种基本数据类型 2、Integer变量必须实例化后才能使用，而int变量不需要
3、Integer实际是对象的引用，当new一个Integer时，实际上是生成一个指针指向此对象；而int则是直接存储数据值 4、Integer的默认值是null，int的默认值是0（这一条说明了为啥要加一句 c!=null）
这里提到这个是因为TreeSet<Integer>，泛型只能使用Integer
因为int是基本类型，不包含集合框架中所需要的方法。以这里为例，连hashCode都没有实现，如何计算散列值？所以需要用Integer。泛型里的类型都必须为Object的子类。
TreeSet 自平衡二叉搜索树
这是真的java的这些集合封装好了，是真的好用，而C，哎，自己造轮子吧
class Solution { public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { TreeSet<Integer> set = new TreeSet<>(); for(int i=0;i<nums.length;i++){ Integer c = set.ceiling(nums[i]); if(c!=null && (long)c-(long)nums[i]<=t) return true; Integer f = set.floor(nums[i]); if(f!=null && (long)nums[i]-(long)f<=t) return true; set.add(nums[i]); if(set.size()>k) set.remove(nums[i-k]); } return false; } }
所以这是方便了个锤子？按理说，现在维持的set是非常好找这个c和f的，比原来再加一个循环看起来是要更便捷的，可能这个函数ceiling和floor背后实现很麻烦？？
3.桶（真的是的 第一次见+第一次用 桶排序 ）
非常多的小细节啊
1.泛型必须用Object的子类型，所以只能用Long，不能用long
2.这里w=t+1,这个桶里应该放的数的范围在nums[i]~nums[i]+t,即为t个长度
3.这里还是用了一个滑动窗口，这个窗口还是k大小，但是这里用了桶排序，所以窗口大小就变成了桶的个数
4.特别需要注意的是，每个桶里只放了一个数，这是因为当你发现有第二个数可以放进这个桶时，证明你已经找到了满足k和t的这个数，可以return了，所以一个桶里只会有一个数，所以才可以用get（key）直接取，不然一堆数，还要加个循环（我才开始一直没想明白来着）
5.if(i>=k) map.remove(getId(nums[i-k],w)); 这个地方，我才开始也不理解为啥这个条件是i>=k,其实跟着测试例子走一遍就知道了，从一开始你没有k个桶的时候，你不需要remove，但是当i>=k时，这时，你已经有了k个桶，但还没找到满足条件的数，你需要舍弃最开始的那个桶
6. return (num+1)/w-1; 这里getId的负数处理，我才开始也没懂，其实是把负数一起往右移，仿佛是-3，-2，-1--->-2,-1,0
大概是这个感觉，然后就除以w，但是0已经用过了，就又将结果直接往左移
class Solution { public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { Map<Long,Long> map = new HashMap<>(); //w为桶的长度，应该为t+1,这个桶里应该放的数的范围nums[i]~nums[i]+t,即为k个 int w=t+1; for(int i=0;i<nums.length;i++){ //1.首先拿到m long n = getId(nums[i],w); //2.判断map的对应的编号的桶里有没有这个编号的桶 if(map.containsKey(n)) return true; //3.判断左右近邻的桶中有没有满足要求的数 if(map.containsKey(n+1)&&Math.abs(map.get(n+1)-nums[i]) <= t) return true; if(map.containsKey(n-1)&&Math.abs(nums[i]-map.get(n-1)) <= t) return true; //4.如果nums[i]不满足要求,把nums[i]放入n编号的桶中 map.put(n,(long)nums[i]); if(i>=k) map.remove(getId(nums[i-k],w)); } return false; } private long getId(int num,int w){ if(num>=0){ return num/w; }else{ //把所有的负数向右移1，从0的位置开始，但是算出来的数包含0，就整体减1 return (num+1)/w-1; } } }
今天这3个题，真是做了很久了，幸亏国庆，比较闲，能静下心来好好做题，哈哈哈哈哈哈哈哈
