存在重复元素 III

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] -nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
如果存在则返回 true，不存在返回 false。

示例 1：

输入：nums = [1,2,3,1], k = 3, t = 0
输出：true

示例 2：

输入：nums = [1,0,1,1], k = 1, t = 2
输出：true

示例 3：

输入：nums = [1,5,9,1,5,9], k = 2, t = 3
输出：false

提示：

• 0 <= nums.length <= 2*10^4
• -2^31 <= nums[i] <= 2^31-1
• 0 <= k <= 10^4
• 0 <= t <= 2^31 - 1

解法一：桶排序

class Solution {
    long size;
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int n=nums.length;
        Map<Long,Long> map=new HashMap<>();
        //防止溢出
        size=(long)(t+1);
        for(int i=0;i<n;i++){
            long num=nums[i]*1l;
            long index=getIndex(num);
            //目标桶已经存在，说明已经有了[num-t,num+t]范围的数
            if(map.containsKey(index)) return true;
            long l=index-1,r=index+1;
            //检查相邻的桶
            if(map.containsKey(l)&&num-map.get(l)<=t) return true;
            if(map.containsKey(r)&&map.get(r)-num<=t) return true;
            //建立目标桶
            map.put(index,num);
            //移除下标差在k之外的桶
            if(i>=k)map.remove(getIndex(nums[i-k]*1l));
        }
        return false; 
    }
    public long getIndex(long num){
        //可以假设size=10, 因为非负数是0~9，10~19...这种一组，而负数是-1~-10, -11~-20...这种一组，如果-1~-10直接除以10，会分到两组中，而不是-1这一组，所以先+1变成-0--9,与正数一致，再除以10，最后减1，正好是-1这一组，其它组同理
        return num>=0?num/size:(num+1)/size-1;
    }
}

解法二：TreeSet

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Long> treeset=new TreeSet<>();
        for(int i=0;i<nums.length;i++){
            Long x=nums[i]*1L;
            //返回此set中小于或等于给定元素的最大元素，或者null如果没有这样的元素
            Long l=treeset.floor(x);
            //返回此set中大于或等于给定元素的最小元素，或者null如果没有这样的元素
            Long r=treeset.ceiling(x);
            if(l!=null&&x-l<=t) return true;
            if(r!=null&&r-x<=t) return true;
            treeset.add(x);
            if(treeset.size()==k+1) treeset.remove(nums[i-k]*1L);
        }
        return false;
    }
}