给定一个整数数组，判断数组中是否有两个不同的索引 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值最大为 t，并且 i 和 j 之间的差的绝对值最大为 ķ

示例 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

答案：

 1public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
 2    if (nums.length < 2 || k == 0) {
 3        return false;
 4    }
 5    TreeSet<Long> set = new TreeSet<>();
 6    int i = 0;
 7    while (i < nums.length) {
 8        Long floor = set.floor((long) nums[i]);
 9        Long ceiling = set.ceiling((long) nums[i]);
10        if ((floor != null && nums[i] - floor <= t) ||
11                (ceiling != null && ceiling - nums[i] <= t)) {
12            return true;
13        }
14        set.add((long) nums[i++]);
15        if (i > k) {
16            set.remove((long) nums[i - k - 1]);
17        }
18    }
19    return false;
20}

解析：

首先要读懂题的意思，就是说数组中任意选择两个数，在他们的下标不大于k的情况下，他们的值要小于等于t。我们首先想到的定义一个长度为k的窗口，上面代码set.floor(x)表示的是从set集合中找到小于或等于x的最大值，set.ceiling(x)表示从set集合中找到大于或等于x的最小值，因为set集合中的长度最大是k，所以如果满足条件（第10,11行）直接返回true即可。如果不满足条件，把当前值加入到set集合中，因为集合的长度是k，如果大于k，把最前面的移除掉即可（第16行）。代码比较容易理解，下面再来看一种解法。

 1public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
 2    if (k < 1 || t < 0) return false;
 3    Map<Long, Long> map = new HashMap<>();
 4    for (int i = 0; i < nums.length; i++) {
 5        long remappedNum = (long) nums[i] - Integer.MIN_VALUE;
 6        long bucket = remappedNum / ((long) t + 1);
 7        if (map.containsKey(bucket)
 8                || (map.containsKey(bucket - 1) && remappedNum - map.get(bucket - 1) <= t)
 9                || (map.containsKey(bucket + 1) && map.get(bucket + 1) - remappedNum <= t))
10            return true;
11        if (map.entrySet().size() >= k) {
12            long lastBucket = ((long) nums[i - k] - Integer.MIN_VALUE) / ((long) t + 1);
13            map.remove(lastBucket);
14        }
15        map.put(bucket, remappedNum);
16    }
17    return false;
18}

这种解法非常巧妙，相比较第一种解法我更欣赏这种解法，因为一般不太容易想到，他的原理和第一种有点类似，也是先定义一个大小为k的窗口，当窗口的值大于k（第11行判断的是等于k先移除，然后在15行在添加）的时候会把最老的给移除掉，他添加的不是当前的值，而是把当前值映射到一个桶里面，这个桶里面所有元素的最大值相差为k,因为如果在这个桶里有重复的元素，说明存在这样的两个数，直接返回true即可（第7行），如果不在一个桶里，在分别判断他的前一个桶和后一个桶值的差距。注意这里的第5行为什么要减去Integer.MIN_VALUE,是为了防止num[i]出现负数，导致映射的桶为负的。其实这种解法还是相当经典的，希望大家能够理解他。