Tìm các cặp trong mảng có tổng đã tồn tại trong mảng trong C++

Giới thiệu

Cho một mảng arr[] gồm N số nguyên. Nhiệm vụ là tìm tất cả các cặp phần tử trong mảng mà tổng của chúng cũng là một phần tử có mặt trong mảng.

Ví dụ minh họa

Đầu vào

arr[] = {1, 2, 4, 6, 7}

Đầu ra

(1, 6), (2, 4)

Giải thích

• Cặp (1, 6): tổng = 7 (có trong mảng)
• Cặp (2, 4): tổng = 6 (có trong mảng)

Phương pháp 1: Duyệt ba vòng lồng nhau (Brute Force)

Tìm tất cả các cặp có thể từ mảng, tính tổng và tìm kiếm tổng đó trong mảng. Sử dụng bộ đếm để theo dõi số cặp tìm thấy.

Chương trình minh họa

#include <iostream>
using namespace std;

void findSumPairsArr(int arr[], int n) {
    int pairCount = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = 0; k < n; k++) {
                if (arr[i] + arr[j] == arr[k]) {
                    cout << "( " << arr[i] << ", " << arr[j] << " ), sum = " << (arr[i] + arr[j]) << "\n";
                    pairCount++;
                }
            }
        }
    }
    if (!pairCount)
        cout << "No Such Pairs found !";
}

int main() {
    int arr[] = { 1, 2, 4, 6, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Pairs in array whose sum already exists in array : \n";
    findSumPairsArr(arr, n);
    return 0;
}

Đầu ra

Pairs in array whose sum already exists in array -
( 1, 6 ), sum = 7 ( 2, 4 ), sum = 6

Phương pháp 2: Sử dụng bảng băm (Hash Table) - Hiệu quả hơn

Sử dụng unordered_set để lưu trữ các phần tử của mảng, cho phép kiểm tra sự tồn tại của tổng trong O(1) trung bình.

Chương trình minh họa

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

void findSumPairsArr(int arr[], int n) {
    unordered_set HT;
    for (int i = 0; i < n; i++)
        HT.insert(arr[i]);

    int pairCount = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (HT.find(arr[i] + arr[j]) != HT.end()) {
                cout << "( " << arr[i] << ", " << arr[j] << " ), sum = " << (arr[i] + arr[j]) << "\n";
                pairCount++;
            }
        }
    }
    if (!pairCount)
        cout << "No Such Pairs found !";
}

int main() {
    int arr[] = {1, 2, 4, 6, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Pairs in array whose sum already exists in array : \n";
    findSumPairsArr(arr, n);
    return 0;
}

Đầu ra

Pairs in array whose sum already exists in array -
( 1, 6 ), sum = 7 ( 2, 4 ), sum = 6

Độ phức tạp: Phương pháp 1: O(n³), Phương pháp 2: O(n²) trung bình nhờ tra cứu O(1) của unordered_set.