# 0220. Contains Duplicate III
###### tags: `Leetcode` `Medium` `TreeMap` `Sliding Window`
Link: https://leetcode.com/problems/contains-duplicate-iii/
## 思路 $O(Nlogk)$ $O(k)$
维持一个长度为k的sliding window
把window里的所有值都放进treeset里面
对于一个新的值 找它的$floor$和$ceil$ 如果$floor \geq num-t$或者$ceil \leq num+t$ 都return true
这里要注意的是 因为有可能涉及nums的最大值有可能是Integer.MAX_VALUE, 最小值有可能是Integer.MIN_VALUE, 如果再+或-t就会overflow, 所以这里都用Long
## Code

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Long> set = new TreeSet<>();
        for(int i=0; i<nums.length; i++){
            long num = (long)nums[i];
            Long floor = set.floor(num);
            Long ceil = set.ceiling(num);
            if ((floor != null && floor >= num-t)
                    || (ceil != null && ceil <= num+t)) {
                return true;
            }
            set.add(num);
            if(set.size()==k+1) set.remove((long)nums[i-k]);
        }
        return false;
    }
}