In tất cả cặp số có tổng cho trước trong C++

Cho mảng số nguyên và tổng S. In tất cả cặp (a, b) có a + b = S.

Input: array = {1, 6, -2, 3} sum = 4 Output: (1, 3), (6, -2)

Cách 1: 2 vòng lặp O(n^2). Cách 2: Hashing O(n) - dùng unordered_map lưu tần suất.

Chương trình minh họa (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, sum = 4;
    cout << "Các cặp có tổng " << sum << ":\n";
    printPairsWithSum(arr, n, sum);
    return 0;
}

Kết quả

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