Contains Duplicate III

[https://leetcode.com/problems/contains-duplicate-iii/]
给定一个int类型数组，求是否存在两个index，他们对应的value差的绝对值不大于t，index差不大于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

解法1

暴力方法，

解法2 - 平衡树

复杂度O(nlogk)
index为i,j 所以需要保证j - i <=k , |nums[j] - nums[i]| <= t
条件变化一下:j-i<=k, nums[i]-t <=nums[j] <=t + nums[i]
-j- i <=k,所以一直位置平衡树的节点个数为k，所有的结果都在节点中找

• 平衡树中能找到所有大于当前节点的最小值tree.ceiling
• 遍历nums ， 找到nums[i] - t <= nums[j] ，对(nums[i] - t) 用ceiling函数，找到大于这个值的最小值X， 如果X <= nums[i] + t，那就找到我们的答案了

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (k <= 0 || t < 0) return false;
        TreeSet<Long> tree = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            Long x = tree.ceiling((long) nums[i] - t);
            if (x != null && x <= (long) nums[i] + t) {
                return true;
            }
            if (i >= k) {
                tree.remove((long) nums[i - k]);
            }
            tree.add((long) nums[i]);
        }
        return false;
    }

解法3 桶排序

• 将nums中的数字放到对应的桶中，桶的个数按照t+1分隔，分隔为t+1是因为防止t==0
• |nums[i] - nums[j]| <=t 那么nums[i]和nums[j]一定在同一个桶或者相邻的桶中，例:t=4 则桶中能对应的值是 , [0,5],[6,10],[11,15],[16,20]....差值小于等于4的两个数字一定在响铃的桶中
• 考虑到nums[i]可能为负数，如果num为负数，那么key -= 1，因为比C++/Java 的负数取整是：-2 /3 = 0，这题这样是不行的。
• 本题有一点特殊的是，一个桶在循环的过程中，一定只有一个数字，如果出现
• 始终保持有k个桶
  第二个，则结果就出来了
  talk is cheap,show me your example

Input: nums = [1,5,9,6,5,9], k = 2, t = 3
Output: true
---------------------------------------
i = 0,nums[i] = 1, 1 /  4 =0,map[0] = 1
---------------------------------------
i = 1,nums[i] = 5, 5 /  4 =1,map[1] = 5 
         map[0]有数字，但是|1-5| > 3不符合条件
         map[2]没有数字 
---------------------------------------
i = 2,nums[i] = 9, 9 /  4 =1,map[2] = 9
        map[1]有数字，   |5-9|  > 4 不符合条件
        map[3]没有数字
此时  i  >=k 需要去掉 map[i-k] / (t+1)对应的那个值,remove(map(0))
---------------------------------------
i = 3,nums[i] = 6,6/4=1，map[1]中已经有5 了，所以return true

上代码

public boolean containsNearbyAlmostDuplicate2(int[] nums, int k, int t) {
        if (k <= 0 || t < 0) {
            return false;
        }

        HashMap<Long, Long> keyToNum = new HashMap<>();
        long div = (long) t + 1;
        for (int i = 0; i < nums.length; i++) {
            long num = (long) nums[i];
            long key = num / div;
            if (num < 0) key--;
            if (keyToNum.containsKey(key)
                    || keyToNum.containsKey(key + 1) && keyToNum.get(key + 1) - num <= t
                    || keyToNum.containsKey(key - 1) && num - keyToNum.get(key - 1) <= t) {
                return true;

            }
            if (i >= k) {
                long key2 = ((long) nums[i - k]) / div;
                keyToNum.remove(nums[i - k] < 0 ? key2 - 1 : key2);
            }
            keyToNum.put(key, num);
        }
        return false;
    }

https://www.hrwhisper.me/leetcode-contains-duplicate-i-ii-iii/