在C++中包含重复的III(Duplicate III)

假设我们有一个整数数组，我们必须检查数组中是否有两个不同的索引i和j，以使nums [i]和nums [j]之间的绝对差最大为t。i和j之间的绝对差最大为k。因此，如果输入类似于[1,2,3,1]，则如果k = 3且t = 0，则返回true。

为了解决这个问题，我们将遵循以下步骤-

• 设置一个s，n：= nums数组的大小

• 对于i，范围为0至n – 1

• x：=下一个元素为随机

• 如果从x开始的第t个元素> = nums [i]，则返回true

• x是从nums [i]开始的set元素的索引

• 如果x不在集合的范围内，并且x的值<<nums [i] + t，则返回true

• 如果x不是第一个元素

• 在s中插入nums [i]，然后从s中删除nums [i-k]

• 返回假

例子（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