leetcodeノート:Contains Duplicate III

一.タイトルの説明
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k .
二.テーマ分析
2つの異なる下付きiおよびjが存在するか否かを判断する整数配列が与えられ、| nums[i] - nums[j] | <= tを満たし、下付き| i - j | <= kを満たす.kの大きさの二叉探索木BSTを維持し、配列中の要素を遍歴し、BST上で条件に合致する数対があるかどうかを探索し、存在すればtrueに戻る.そうしないと、現在の要素数対をBSTに挿入し、このBSTを更新する(このときBSTの大きさがkであれば、値を削除する必要がある).保証BSTの大きさがk以下であることは、中の数の下の標差値が必ず条件を満たすことを保証するためである:| i - j | <= k.実装の場合、mulitsetを使用してBSTを実装することができる.
mulitsetは秩序あるコンテナで、中の要素はすべてソートされ、重複する要素が現れることを許可し、挿入、削除、検索などの操作をサポートし、まるで集合のようです.Multiset内部はバランスツリーで実現される.従って、すべての操作はO(logn)時間以内に厳格に完了し、効率が高い.
三.サンプルコード

//    ，  vector  ，      
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
         if(nums.size() < 2) return false;
         vector<pair<long, int>> value;
         for (int i = 0; i < nums.size(); ++i)
            value.push_back(pair<long, int>(nums[i], i));
         sort(value.begin(), value.end());
         for (int i = nums.size() - 1; i >= 1; --i)
         {
             for (int j = i - 1; j >= 0; --j)
             {
                 if (value[i].first - value[j].first > t) break;
                 else if (abs(value[i].second - value[j].second) <= k) return true;
                 else continue;
             }
         }
         return false;
    }
};

//    
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
    multiset<int> window; //        k   
    for (int i = 0; i < nums.size(); ++i) {
        if (i > k) window.erase(nums[i - k - 1]); //   window     k   ，               k
        auto pos = window.lower_bound(nums[i] - t); 
        if (pos != window.end() && *pos - nums[i] <= t) return true;
        window.insert(nums[i]);
    }
    return false;
}

四.小結
集合クラスsetとmulitsetの使用を練習した.関連タイトル:Contains Duplicate IIとContains Duplicate I