###### tags: `LeetCode` `Medium`
# LeetCode #220 [Contains Duplicate III](https://leetcode.com/problems/contains-duplicate-iii)
### (Medium)
給你一個整數數組 nums 和兩個整數 k 和 t 。請你判斷是否存在 兩個不同下標 i 和 j，使得 abs(nums[i]-nums[j]) <= t ，同時又滿足 abs(i-j) <= k 。

如果存在則返回 true，不存在返回 false。

---
建立一set(元素不重複)大小為k+1(也就是元素間距離最大為k), 遍歷nums, 每次尋找set中第一個大於等於nums[i]-t的值, 若存在則檢查該值減去nums[i]是否小於等於t(由於符合範圍為nums[i]-t ~ nums[i]+t), 若也滿足則回傳true, 反之回傳false。須注意nums[i]-t 或 nums[i]+t有可能超出整數範圍, 因此set的元素類型應設為long long。

---

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if(nums.size()){
            set<long long> windows;
            for(int i=0;i<nums.size();i++){
                if(i>k)windows.erase(nums[i-k-1]);
                auto pos = windows.lower_bound((long long)nums[i]-t);
                if(pos!=windows.end()&& *pos-nums[i]<=t)return 1;
                windows.insert(nums[i]);
            }
            return 0;
        }
        return 0;
    }
};