滑动窗口

我们可以用一个窗口，窗口大小固定为k+1个元素，使用二分在窗口内查找到和nums[i]最近的数。

因为是固定大小滑动窗口，不需要双指针。

从左到右遍历数组：

1. 判断是否有元素滑出窗口
2. 二分窗口内，找到和nums[i]绝对值差最小的数，并判断是否满足绝对值差<=t
3. 插入当前数

时间复杂度$O(NlogK)$，空间复杂度$O(K)$

AC代码

class Solution {
public:
    typedef long long LL;

    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        multiset<LL> set;
        set.insert(1e18); set.insert(-1e18);//哨兵
        k ++;
        for (int i = 0 ; i < nums.size() ; i ++) {
            //窗口左边划出
            if (i - k + 1 > 0) set.erase(set.find(nums[i - k]));
            //找到窗口内和nums[i]最近的数
            auto it = set.lower_bound(nums[i]);
            if (*it - nums[i] <= t) return true;
            it --;
            if (nums[i] - *it <= t) return true;
            //插入
            set.insert(nums[i]);
        }
        return false;
    }
};