C++의 중복 III 포함

정수 배열이 있다고 가정하면 nums[i]와 nums[j] 사이의 절대적 차이가 되도록 배열에 두 개의 고유한 인덱스 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에 삽입한 다음 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

C++의 중복 III 포함

예시(C++)

입력

출력