值和小标之差都在给定范围内之滑动窗口+HashMap+桶排

前言一、案例二、题解总结参考文献

维持一个滑动窗口的值对应的特性存储于map之中，从而避免每次重复计算导致复杂度变高。

维持一个滑动窗口，这个窗口大小为k，记录窗口内的值分别属于哪一类，就不用每次重复去计算，再通过HashMap快速找到左中右桶来寻找是否有满足条件的值对。

//桶排
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int len = nums.length;
        Map cache = new HashMap<>();
        long base = (long) t + 1;
        for (int i = 0; i < len; i++) {
            long id = getId(nums[i], base);
            if (cache.containsKey(id)) return true;
            if (cache.containsKey(id - 1) && nums[i] - cache.get(id - 1) <= t) return true;
            if (cache.containsKey(id + 1) && cache.get(id + 1) - nums[i] <= t) return true;
            cache.put(id, (long) nums[i]);
            if (i - k >= 0) cache.remove(getId(nums[i - k], base));
        }
        return false;
    }

    private long getId(int num, long base) {
        if (num >= 0) return num / base;
        long m = num / base, n = num % base;
        return n == 0 ? m : m - 1;
    }

1）需要去接受新知识，第一次见桶排，虽然很痛苦，但是还是理清逻辑，还完成了自己的改写代码，这种新输入的思想真的很nice。

[1] LeetCode 原题[
[2] LeetCode 官方题解 非常详细