一、题目

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

如果存在则返回 true，不存在返回 false。

点击查看原题

二、思路

该题思路很直观，就是维持一个数据数量为k的有序数据结构，根据新遍历到的数据num[i]，来找到一个nums[j]，使得abs(nums[i] - nums[j]) <= t 。解题方式就是这样，那么首先讨论有序数据结构：
1）有序数据结构需要不断插入和删除值
2）删除值不需要考虑重复元素的情况，因为重复元素一定符合题意返回true，删除之前就已经返回函数结果了

如何进行nums[j]的查找呢？我们需要找的是最靠近num[i]的两个值：即小于num[i]且最大、大于num[i]且最小。可以将这个化为在{num[i] - t, num[i] + t}中寻找值，那么，只需要找一个大于等于num[i] - t的最小整数，然后判断是否小于等于num[i] + t。

三、代码

首先使用TreeSet作为有序数据结构，寻找元素是logn复杂度。

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Long> treemap = new TreeSet();
        for (int i = 0; i < nums.length; i++) {
            Long ceiling = treemap.ceiling((long)nums[i] - (long)t);    // 找一个大于等于num[i] - t的最小整数
            if (ceiling != null && ceiling <= (long)nums[i] + (long)t) {        // 判断是否小于等于num[i] + t
                return true;    
            }
            treemap.add((long)nums[i]);
            if (i >= k) {
                treemap.remove((long)nums[i - k]);
            }
        }
        return false;
    }
}

四、桶思想优化

可将排序结构进一步优化，将所有元素进行分桶，桶大小为t+1，如果两个元素在同一个桶中，则一定符合题意要求返回true（这样一个桶中就一定只有一个元素，因为多个元素的情况直接排除了）；如果隔壁桶有元素，那就取出元素进行加减法判断是否小于t即可。
根据上述思想，可以直接用一个hash表进行存储，这样取和拿的时间可以优化到O(1)。

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        Map<Integer, Long> map = new HashMap();
        for (int i = 0; i < nums.length; i++) {
            int indx = getIndx(nums[i], t);
            if (map.containsKey(indx)) {
                return true;
            }
            // 判断indx - 1桶中是否存在可行解
            if (map.containsKey(indx - 1) && (long)nums[i] - map.get(indx - 1) <= (long)t) {
                return true;
            }
            // 判断indx + 1桶中是否存在可行解
            if (map.containsKey(indx + 1) && map.get(indx + 1) - (long)nums[i]  <= (long)t) {
                return true;
            }
            map.put(indx, (long)nums[i]);
            if (i >= k) {    // 确保只有k个元素
                map.remove(getIndx(nums[i-k], t));
            }
        }
        return false;
    }
    private int getIndx(int val, int t) {        // 桶大小为t+1，根据元素值算出属于哪个桶
        if (val < 0) {        // 由于(-t, 0)和(0, t)在同一个桶中，为了避免，负值的桶下标整体减1
            return val/(t+1) - 1;
        }
        return val/(t+1);
    }
}