หาคู่ในอาร์เรย์ที่ผลรวมมีอยู่ในอาร์เรย์ด้วย C++

ภาพรวมปัญหา

ได้รับอาร์เรย์ arr[] ขนาด N จำนวนเต็ม งานคือหาคู่ขององค์ประกอบที่ผลรวมของคู่นั้นมีอยู่ในอาร์เรย์ด้วย

ตัวอย่าง

อินพุต

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

เอาต์พุต

(1, 6), (2, 4)

คำอธิบาย

คู่ (1, 6) ผลรวม = 7 (มีในอาร์เรย์)
คู่ (2, 4) ผลรวม = 6 (มีในอาร์เรย์)

วิธีแก้ปัญหา

วิธีที่ 1: Triple Nested Loop - O(n³)

หาคู่ทั้งหมดที่เป็นไปได้ (2 loops) แล้วค้นหาผลรวมในอาร์เรย์ (loop ที่ 3)

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

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

วิธีที่ 2: Hash Table (unordered_set) - O(n²)

ใช้ unordered_set เก็บค่าทั้งหมดในอาร์เรย์ แล้วตรวจสอบผลรวมของแต่ละคู่ใน O(1)

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

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

void findSumPairsArr(int arr[], int n) {
    unordered_set<int> 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;
}

เอาต์พุต

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

สรุป

วิธี Hash Table เร็วกว่ามาก เนื่องจากลดการค้นหาจาก O(n) เหลือ O(1) ทำให้ Complexity รวมลดจาก O(n³) เป็น O(n²)