이 문제에서는 정렬되지 않은 배열이 있고 이 배열 내에서 합이 동일한 모든 쌍을 인쇄해야 합니다.
문제를 이해하기 위해 예를 들어 보겠습니다 -
Input: array = [12, 13, 20, 5] Output: [12, 13] and [20, 5] have sum 25.
이 문제를 해결하려면 동일한 합계의 쌍을 찾아야 합니다. 이를 위해 동일한 합계에 대한 쌍을 확인합니다. 그리고 중복 쌍을 피하기 위해 지도를 사용합니다.
이를 위해서는 두 개의 맵이 필요합니다. 하나는 모든 합 쌍과 그 합을 저장하고 다른 하나는 모든 합과 해당 쌍을 저장합니다.
따라서 Map1 → 키 =쌍; 값 → 합계
Map2 → 키 =정수 합계; 값 → 쌍의 벡터
이제 합계 값이 동일한 모든 값을 인쇄하십시오.
예시
위의 논리를 설명하는 프로그램 -
#include <bits/stdc++.h>
using namespace std;
void findEqualSumPairs(int A[], int n){
map<int, vector<pair<int, int> > >map1;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
pair<int, int> p = make_pair(A[i], A[j]);
map1[A[i] + A[j]].push_back(p);
}
}
for (auto value = map1.begin(); value != map1.end(); value++) {
if (value->second.size() > 1) {
for (int i = 0; i < value->second.size(); i++) {
cout<<"[ "<<value->second[i].first<<", "<<value->second[i].second<<"] ";
}
cout<<"have sum : "<<value->first<<endl;
}
}
}
int main() {
int A[] = { 6, 4, 12, 10, 22,11, 8, 2 };
int n = sizeof(A) / sizeof(A[0]);
cout<<"Pairs with same sum are : \n";
findEqualSumPairs(A, n);
return 0;
} 출력
합이 같은 쌍은 -
[ 6, 4] [ 8, 2] have sum : 10 [ 4, 8] [ 10, 2] have sum : 12 [ 6, 8] [ 4, 10] [ 12, 2] have sum : 14 [ 6, 10] [ 4, 12] have sum : 16 [ 6, 12] [ 10, 8] have sum : 18