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;
    }
};