[LeetCode] Contains Duplicate III

This problem gets much trickier than Contains Duplicate and Contains Duplicate II. 

The basic idea is to maintain a window of k numbers. For each new number, if there exists a number in the window with difference not larger than k, then return true. When we check every number and have not returned true, return false. Remember that we need to update the windows (erase the earliest added element) after it has more than k elements.

The code is actually pretty short if we take advantage of the STL set template and its method lower_bound.

 1     bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
 2         set<long long> windows;
 3         for (int i = 0; i < nums.size(); i++) {
 4             auto pos = windows.lower_bound(nums[i] - t);
 5             if (pos != windows.end() && *pos <= (long long)nums[i] + t)
 6                 return true;
 7             windows.insert(nums[i]);
 8             if (i >= k) windows.erase(nums[i - k]);
 9         }
10         return false;
11     }

[LeetCode] Contains Duplicate III

原文：http://www.cnblogs.com/jcliBlogger/p/4562930.html