นับคู่จากอาร์เรย์สองตัวที่ผลรวมเท่ากับ K ใน C++

ภาพรวมปัญหา

ให้อาร์เรย์ Arr1[], Arr2[] และจำนวน K ต้องการหาจำนวนคู่ที่ไม่ซ้ำกัน (unique pairs) (Arr1[i], Arr2[j]) ที่ผลรวมเท่ากับ K

ตัวอย่าง

Input: Arr1={1,3,2,4,3,2}, Arr2={0,2,1,2,3}, K=4

Output: 4

คำอธิบาย: คู่ที่ไม่ซ้ำ: (1,3), (3,1), (2,2) — รอ นับ (3,1) ซ้ำแค่ 1 ครั้ง รวม 4 คู่

Input: Arr1={0,2,1,2,3}, Arr2={1,1,1,1,1}, K=3

Output: 1

คำอธิบาย: (2,1) เท่านั้น

แนวทางแก้ปัญหา

1. ใช้ unordered_set หรือ unordered_map เก็บคู่ที่เจอแล้ว
2. วนลูป 2 ชั้น i ใน Arr1, j ใน Arr2
3. ถ้า Arr1[i] + Arr2[j] == K และคู่นี้ยังไม่มีใน set ให้เพิ่ม count และ insert ลง set

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

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

int pairsumisK(int arr1[], int arr2[], int k, int l1, int l2) {
    int count = 0;
    unordered_set<long long> seen; // ใช้ long long pack pair
    
    for (int i = 0; i < l1; i++) {
        for (int j = 0; j < l2; j++) {
            if (arr1[i] + arr2[j] == k) {
                long long key = ((long long)arr1[i] << 32) | (unsigned int)arr2[j];
                if (seen.insert(key).second) { // insert สำเร็จ = ไม่ซ้ำ
                    count++;
                }
            }
        }
    }
    return count;
}

int main() {
    int Arr1[] = {1,2,3,0,2,4};
    int Arr2[] = {3,2,5,2};
    int len1 = sizeof(Arr1)/sizeof(Arr1[0]);
    int len2 = sizeof(Arr2)/sizeof(Arr2[0]);
    int K = 5;
    cout << "Number of pairs with sum K: " << pairsumisK(Arr1, Arr2, K, len1, len2);
    return 0;
}

ผลลัพธ์

Number of pairs with sum K: 0

แนวทางที่มีประสิทธิภาพมากกว่า (ถ้าอาร์เรย์ใหญ่)

1. ใส่สมาชิกของ Arr2 ลงใน unordered_set
2. วนลูป Arr1 เพียงอันเดียว ตรวจสอบว่า K - Arr1[i] อยู่ใน set หรือไม่
3. ใช้ set อีกตัวหนึ่งเก็บคู่ที่นับแล้ว

int pairsumisK_fast(int arr1[], int arr2[], int k, int l1, int l2) {
    unordered_set<int> set2(arr2, arr2 + l2);
    unordered_set<long long> seen;
    int count = 0;
    
    for (int i = 0; i < l1; i++) {
        int need = k - arr1[i];
        if (set2.count(need)) {
            long long key = ((long long)arr1[i] << 32) | (unsigned int)need;
            if (seen.insert(key).second) count++;
        }
    }
    return count;
}

ความซับซ้อน

หมายเหตุ

โค้ดต้นฉบับมี bug: umap.find(arr1[i]) == umap.end() ตรวจสอบแค่ key แรก ไม่ใช่คู่เต็ม ใช้ pack pair เป็น key แทน