Leetcode 220 Solution

This article provides solution to leetcode question 220 (contains-duplicate-iii)
Categories:
Tags:
Access this page by simply typing in "lcs 220" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/contains-duplicate-iii

Solution

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if (k == 0)
            return false;

        set<int64_t> a;

        for (int i = 0; i < nums.size(); i++)
        {
            auto it = a.lower_bound((int64_t)nums[i] - t);

            if (it != a.end() && *it <= (int64_t)nums[i] + t)
                return true;

            if (i >= k)
                a.erase(nums[i - k]);

            a.insert(nums[i]);
        }

        return false;
    }
};