418

题目地址：https://leetcode-cn.com/problems/contains-duplicate-iii/
由于要判断的两个数的下标的距离小于k，很容易想到使用滑动窗口，对每个窗口内的数进行判断，然后移动窗口，复杂度就是$O(kn)$，这会超出时间限制

因此降低复杂度就要从滑动窗口入手，使用一种数据结构可以满足一下几点

• 能够用更短的时间判断
• 还可以动态维护，即进行插入删除

想到使用 set 来维护，set可以自动对滑动窗口内的数进行排序，总体复杂度$O(log_{k}n)$
设窗口又端点的数为x，使用lower_bound 函数找到窗口内最小的一个大于等于x-t的数，如果这个数也小于等于x+t，那么就找到了这一对数。

c++

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        set<long> st;
        for (int i = 0; i < nums.size(); i++) {
            auto iter = st.lower_bound((long)nums[i] - t);
            if (iter != st.end() && *iter <= (long)nums[i] + t)
                return true;
            st.insert(nums[i]);
            if (st.size() > k)
                st.erase(nums[i - k]);
        }
        return false;
    }
};

使用set仍然无法达到线性时间，我们可以使用桶排序在O(1)的时候进行类似窗口内判断的操作。
我们将桶的大小设为t+1(因为判断的两个数的差小于等于t，那么桶里放t+1个数就一个都不会漏了)。如果两个元素同属一个桶，那么这两个元素必然符合条件。如果两个元素属于相邻桶，那么我们需要校验这两个元素是否差值不超过 t。如果两个元素既不属于同一个桶，也不属于相邻桶，那么这两个元素必然不符合条件。
难点在于怎么给桶编号，如果是非负数，那么id就是x/t+1,
可以看下这个题解：https://leetcode-cn.com/problems/contains-duplicate-iii/solution/c-li-yong-tong-fen-zu-xiang-xi-jie-shi-b-ofj6/

c++

class Solution {
public:
    int getID (long x, long t) {
        return x >= 0 ? x / (t + 1) : (x + 1) / (t + 1) - 1;
    }
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        unordered_map <long, long> map;//由于桶如果有两个相同的就满足返回true了，所以每个桶里最多放一个元素，使用map就合适
        for (int i = 0; i < nums.size(); i++) {
            int id = getID(nums[i], t);
            if (map.find(id) != map.end()) return true;
            int l = id - 1;
            int r = id + 1;
            if (map.find(l) != map.end() && nums[i] - map[l] <= t) return true;
            if (map.find(r) != map.end() && map[r] - nums[i] <= t) return true;
            map[id] = nums[i];
            if(i - k >= 0) {
                map.erase(getID(nums[i - k], t));
            }
        }
        return false;
    }
};