พิมพ์คู่ในอาร์เรย์ที่มีผลรวมเท่ากันใน C++

ภาพรวมปัญหา

ได้รับ Unsorted Array ต้องพิมพ์คู่ทั้งหมดที่มีผลรวมเท่ากัน

ตัวอย่าง

Input: [12, 13, 20, 5]
Output: [12, 13] and [20, 5] have sum 25

วิธีแก้ปัญหา (Two Maps)

1. Map1: Key = Pair, Value = Sum
2. Map2: Key = Sum, Value = Vector of Pairs
3. ลูปหาคู่ทั้งหมด เก็บใน Map2
4. พิมพ์ Sum ที่มีคู่มากกว่า 1 คู่

ตัวอย่างโค้ด C++

#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;
}

ผลลัพธ์ (Output)

Pairs with same sum are:
[ 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