LeetCode 220. 存在重复元素 III

LeetCode 220. 存在重复元素 III

思路：

用multiset维护一个滑动窗口，然后使用S.lower_bound()函数来找到在窗口内的第一个大于等于x的数，判断差然后再判断第一个小于x的数。

代码：

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        int n = nums.size();
        multiset<long long> S;
        S.insert(1e18),S.insert(-1e18);
        for(int i = 0,j = 0; i < n;i++){
            if(abs(i - j) > k) S.erase(S.find(nums[j++]));
            int x = nums[i];
            auto y = S.lower_bound(x);
            if(*y - x <= t) return true;
            y--;
            if(x - *y <= t) return true; 
            S.insert(x);
        }
        return false;
    }
};