LeetCode 220. Contains Duplicate III

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        const int n = nums.size();
        set<int> s;
        for (int i = 0; i < n; ++i) {
            // limit [nums[i] - t, nums[i] + t] within INT
            auto it = s.lower_bound(max(nums[i], INT_MIN + t) - t);
            if (it != s.end() && *it <= min(nums[i], INT_MAX - t) + t)
                return true;
            s.insert(nums[i]);
            if (i >= k)
                s.erase(nums[i - k]);
        }
        return false;
    }
};