220. Contains Duplicate III (M)

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true
Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true
Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

Constraints:

0 <= nums.length <= 2 * 104
-231 <= nums[i] <= 231 - 1
0 <= k <= 104
0 <= t <= 231 - 1

---

我的方法：

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        multiset<long long int> window;
        
        for (int i=0; i<nums.size(); ++i) {
            long int curr_num = nums[i];
            if (window.size() > k and i-k-1>=0) {
                window.erase(window.lower_bound(nums[i-k-1]));
            }
            
            if (!window.empty()) {
                long int min_num = *(window.begin());
                long int max_num = *(window.rbegin());
                long int left_num = max({min_num, min({max_num, curr_num-t})});
                long int right_num = max({min_num, min({max_num, curr_num+t})});
                    
                long int left = *window.lower_bound(left_num);
                long int right = *window.lower_bound(right_num);
                if (right != right_num) {
                    auto it =  window.lower_bound(right_num);
                    --it;
                    right = *it;
                }
                if (abs(left-curr_num)<=t or abs(right-curr_num)<=t) {
                    return true;
                }
            }
            window.insert(curr_num);
            
        }
        
        return false;
    }
};

Runtime: 80 ms, faster than 14.84% of C++ online submissions for Contains Duplicate III.
Memory Usage: 15.5 MB, less than 12.05% of C++ online submissions for Contains Duplicate III.

主要思想：用multiset当bucket，sliding window里面动态维护一个mutliset，然后对每个元素找window里面的元素-t 和 元素+t 的lowerbound。

    multiset<int> window = {0,2,4,6};
    cout << *window.lower_bound(1) << endl;
    cout << *window.lower_bound(5) << endl;

的输出是2和6

注意事项是

• *window.lower_bound(7)是undefined number，所以不管怎么样都不能超出window max的的范围
• right_num其实也不能低于window min，否则就会right=begin，*（begin-1）也是undefined
• 所以结合上面两点必须对curr_num-t ~ +t的氛围clip到window min ~ window max的范围
• 不知道为什么*(window.lower_bound(right_num) - 1)报错
  • 因为set multiset是没法random access的，所以需要用std::prev std::next std::advance
  • https://stackoverflow.com/questions/53725453/c-set-iterator-error-no-match-for-operator

  •             if (right_ != right_num) {
                    right_ = *prev(window.lower_bound(right_num));
                }
    

---

看答案
https://zxi.mytechroad.com/blog/hashtable/leetcode-220-contains-duplicate-iii/
确实是用multiset，但是用法更巧妙：

• 首先，set/multiset.insert是有返回值的，就是插入点的iterator
• 然后其实比较插入点前后就可以了，因为是最近的两个
• 所以复杂度是O(nlogk)

结合答案的修改：

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        multiset<long> window;
        
        for (int i=0; i<nums.size(); ++i) {
            long curr_num = nums[i];
            if (window.size() > k) {
                window.erase(window.lower_bound(nums[i-k-1]));
            }
            
            auto it = window.insert(curr_num);
            if (it != window.begin() and curr_num-*prev(it) <= t){
                return true;
            }
            if (next(it) != window.end() and *next(it)-curr_num <= t){
                return true;
            }
        }
        
        return false;
    }
};

NOTE：

• window.erase(window.lower_bound(nums[i-k-1])); 和 window.erase(window.find(nums[i-k-1]));基本是一回事，find在multiset里面就随便找到一个就可以了