C++のDuplicateIIIが含まれています

整数の配列があるとすると、nums[i]とnums[j]の絶対差が大きくなるように、配列に2つの異なるインデックスiとjがあるかどうかを確認する必要があります。はせいぜいtです。そして、iとjの絶対差は最大でkです。したがって、入力が[1,2,3,1]のようである場合、k=3およびt=0の場合、trueを返します。

これを解決するには、次の手順に従います-

• セットを作成しますs、n：=nums配列のサイズ

• 0からn–1の範囲のiの場合

  • xは、nums[i]以上で始まる集合要素のインデックスです

  • xがx<=nums [i] + tのセットと値の範囲内にない場合は、trueを返します

  • xが最初の要素でない場合

    • x：=ランダムとしての次の要素

    • xから始まるt番目の要素が>=nums [i]の場合、trueを返します

  • nums [i]をsに挿入し、nums[i-k]をsから削除します

• falseを返す

例（C ++）

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
      multiset <int> s;
      int n = nums.size();
      for(int i = 0; i< n; i++){
         multiset <int> :: iterator x = s.lower_bound(nums[i]);
         if(x != s.end() && *x <= nums[i] + t ) return true;
            if(x != s.begin()){
               x = std::next(x, -1);
               if(*x + t >= nums[i])return true;
            }
            s.insert(nums[i]);
            if(i >= k){
               s.erase(nums[i - k]);
            }
         }
         return false;
      }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3,1};
   cout << (ob.containsNearbyAlmostDuplicate(v, 3,0));
}

入力

[1,2,3,1]
3
0

出力

1