Trong bài toán này, chúng ta có một mảng chưa được sắp xếp và chúng ta phải in tất cả các cặp trong mảng này có tổng bằng nhau.
Hãy lấy một ví dụ để hiểu vấn đề -
Input: array = [12, 13, 20, 5] Output: [12, 13] and [20, 5] have sum 25.
Để giải quyết vấn đề này, chúng ta sẽ phải tìm các cặp có tổng bằng nhau. Đối với điều này, chúng tôi sẽ kiểm tra các cặp để có tổng bằng nhau. Và để tránh các cặp trùng lặp, chúng tôi sẽ sử dụng bản đồ.
Đối với điều này, chúng ta sẽ cần hai bản đồ, một bản đồ để lưu trữ tất cả các cặp tổng và tổng của chúng và bản đồ khác để lưu trữ tất cả tổng và các cặp tương ứng của chúng.
Vì vậy, Map1 → key =pair; giá trị → tổng
Map2 → key =sum integer; giá trị → vectơ của cặp
Bây giờ, hãy in tất cả các giá trị có cùng giá trị tổng.
Ví dụ
Chương trình minh họa logic trên -
#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;
} Đầu ra
Các cặp có tổng bằng nhau là -
[ 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