# 220. Contains Duplicate III

{% hint style="info" %}
Key idea: use map to store a sliding window with size of k. map.lower\_bound()

很难理解这个函数的作用以及本题的解题思路，思路见链接：<https://www.cnblogs.com/grandyang/p/4545261.html>
{% endhint %}

{% tabs %}
{% tab title="C++" %}

```cpp
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        map<long long, int> m;
        int base = 0;
        for(int i = 0; i < nums.size(); i ++) {
            if(i - base > k) m.erase(nums[base++]);
            auto a = m.lower_bound((long long)nums[i]-t);
            if(a != m.end() && abs(a->first - nums[i]) <= t) 
                return true;
            m[nums[i]] = i;
        }
        return false;
    }
};
```

{% endtab %}
{% endtabs %}