220. Contains Duplicate III

The naive way is to check all pairs in the list. But this way gets TLE.

1:  class Solution {  
2:  public:  
3:    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {  
4:      for (int i = 0; i < nums.size(); i++) {  
5:        for (int j = i+1; j < nums.size(); j++)  
6:          if (abs((long long)nums[i]-nums[j]) <= t && abs(i-j) <= k) return true;  
7:      }  
8:      return false;  
9:    }  
10:  };  

The idea behind the top voted way is to scan from left to right and to keep a sorted window nums[j...i] that has size of k. This window ensures that all the numbers offsets is at most k. Since the numbers in the window are sorted, we only need to find the first number that is larger or equal than nums[i]-t. The reason is if a >= nums[i]-t, then we have a-nums[i] >= -t or nums[i]-a <= t. And if we can make sure that a-nums[i] <= t, then we have |a-nums[i]| <=t. We can use binary search to achieve this number.

1:  class Solution {  
2:  public:  
3:    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {  
4:      map<int, int> m;  
5:      int j = 0;  
6:      for (int i = 0; i < nums.size(); i++) {  
7:        if (i - j > k) m.erase(nums[j++]);  
8:        auto it = m.lower_bound(nums[i]-t);  
9:        if (it != m.end() && abs(it->first - nums[i]) <= t) return true;  
10:        m[nums[i]] = i;  
11:      }  
12:      return false;  
13:    }  
14:  };