Contains Duplicate III (Leetcode

参考： http://www.cnblogs.com/grandyang/p/4545261.html

双指针，或者用map lower bound找。lower bound找到的是比k大中(>= k)，最小的数。

bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if(nums.empty()) return false;
        map<int, int> mp;
        int start = 0;
        for(int i=0; i<nums.size(); i++){
            if(i-start > k){
                mp.erase(nums[start++]);
            }
            auto it = mp.lower_bound(nums[i]-t);
            if(it != mp.end()){
                if(abs(nums[i] - it->first) <= t) return true;
            }
            mp[nums[i]] = i;
        }
        return false;
    }

第二种是不用lower bound的双指针扫描

bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if(nums.empty()) return false;
        int left = 0;
        for(int i=1; i<nums.size(); i++){
            if(labs(nums[i]-nums[left]) <= t && i-left <= k) return true;
            if(i-left >= k){
                for(int j=left+1; j<i; j++){
                    if(labs(nums[i]-nums[j]) <= t && i-j <= k) return true;
                }
                left = i-k+1;
            }
        }
        return false;
    }