배열과 정수 k가 있다고 가정하고 배열에서 고유한 k-diff 쌍의 수를 찾아야 합니다. 여기서 k-diff 쌍은 (i, j)와 같습니다. 여기서 i와 j는 모두 배열에 존재하고 절대 차이는 k입니다.
따라서 입력이 [3,1,4,1,5], k =2와 같으면 배열과 같은 (1,3) 및 ( 3,5).
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
보고 완료라고 하는 지도 정의
-
한 세트 정의
-
k <0이면 -
-
0 반환
-
-
initialize i :=0의 경우, i
-
(보이는[nums[i]] 1씩 증가)
-
s
에 숫자[i]를 삽입합니다.
-
-
답변 :=0
-
s에 있는 각 요소에 대해 다음을 수행합니다. -
-
k가 0과 같으면 -
-
본 경우[it]> 1이면 -
-
(1만큼 증가)
-
-
-
그렇지 않으면
-
완료[it] 1 증가
-
(it + k)가 표시되지만 완료되지 않은 경우 -
-
(1만큼 증가)
-
-
(it - k)가 표시되지만 완료되지 않은 경우 -
-
(1만큼 증가)
-
-
-
-
반환
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h&g;
using namespace std;
class Solution {
public:
int findPairs(vector<int>& nums, int k) {
map<int, int> seen, done;
set<int> s;
if (k < 0)
return 0;
for (int i = 0; i < nums.size(); i++) {
seen[nums[i]]++;
s.insert(nums[i]);
}
int ans = 0;
for (auto it = s.begin(); it != s.end(); it++) {
if (k == 0) {
if (seen[*it] > 1)
ans++;
}
else {
done[*it]++;
if (seen.find(*it + k) != seen.end() && done.find(*it + k) == done.end())
ans++;
if (seen.find(*it - k) != seen.end() && done.find(*it - k) == done.end())
ans++;
}
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {3,1,4,1,5};
cout << (ob.findPairs(v, 2));
} 입력
{3,1,4,1,5}, 2 출력
2