พิมพ์ Pairs ทั้งหมดที่มีผลรวมกำหนดใน C++

ในปัญหานี้ เราจะได้รับ array ของจำนวนเต็มและจำนวนเต็ม sum และต้องพิมพ์ pairs ทั้งหมดของจำนวนเต็มที่ผลรวมเท่ากับค่า sum

ตัวอย่างเพื่อความเข้าใจ

Input - array = {1, 6, -2, 3} sum = 4

Output - (1, 3), (6, -2)

ที่นี่ เราต้องการ pairs ที่มีผลรวมเท่ากับค่าที่กำหนด

วิธีง่ายคือตรวจสอบ pairs ขององค์ประกอบที่สร้างผลรวมได้ สามารถทำได้โดยท่อง array และหาตัวเลขใน array ที่บวกกันได้ค่า sum

โปรแกรมตัวอย่าง (วิธีที่ 1 - Brute Force)

#include <iostream>
using namespace std;

int printPairsWithSum(int arr[], int n, int sum) {
    int count = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (arr[i] + arr[j] == sum)
                cout << "[ " << arr[i] << ", " << arr[j] << " ]\n";
}

int main() {
    int arr[] = {1, 6, -2, 3};
    int n = 4;
    int sum = 4;
    cout << "Pairs with Sum " << sum << " are :\n";
    printPairsWithSum(arr, n, sum);
    return 0;
}

ผลลัพธ์

Pairs with Sum 4 are :
[ 1, 3 ]
[ 6, -2 ]

วิธีนี้เข้าใจง่ายแต่ไม่ค่อยมีประสิทธิภาพ อีกวิธีคือใช้ hashing

เราจะสร้าง hash table และท่อง array หา pairs ในมัน เมื่อ match ให้พิมพ์ array:

โปรแกรมตัวอย่าง (วิธีที่ 2 - Hashing)

#include <bits/stdc++.h>
using namespace std;

void printPairsWithSum(int arr[], int n, int sum) {
    unordered_map<int, int> pair;
    for (int i = 0; i < n; i++) {
        int rem = sum - arr[i];
        if (pair.find(rem) != pair.end()) {
            int count = pair[rem];
            for (int j = 0; j < count; j++)
                cout << "[" << rem << ", " << arr[i] << " ]\n";
        }
        pair[arr[i]]++;
    }
}

int main() {
    int arr[] = {1, 6, -2, 3};
    int n = 4;
    int sum = 4;
    cout << "The pair with sum is \n";
    printPairsWithSum(arr, n, sum);
    return 0;
}

ผลลัพธ์

Pairs with Sum 4 are :
[ 1, 3 ]
[ 6, -2 ]