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

เราได้รับอาร์เรย์ของจำนวนเต็ม และงานคือการนับจำนวนคู่ที่แตกต่างกัน (distinct pairs) ในอาร์เรย์ที่ผลรวมของคู่นั้นก็มีอยู่ในอาร์เรย์เดียวกันด้วย

ข้อสังเกตสำคัญ

• คู่จะนับเพียงครั้งเดียวไม่สนใจลำดับ เช่น (3,2) และ (2,3) นับเป็น 1 คู่
• ถ้ามีตัวเลขซ้ำหลายครั้ง ให้พิจารณาเพียง 2 ครั้งเพื่อสร้างคู่เดียว เช่น {2,2,2,2} คู่คือ (2,2) นับ 1 ครั้ง

ตัวอย่าง

Input − int arr = {6, 4, 10, 14} Output − count is 2

คำอธิบาย − คู่ที่ผลรวมอยู่ในอาร์เรย์คือ (6,4) ผลรวม 10 และ (10,4) ผลรวม 14 นับได้ 2 คู่

Input − int arr = {6, 6, 6, 6, 6, 13} Output − count is 0

คำอธิบาย − ไม่มีคู่ใดที่ผลรวมอยู่ในอาร์เรย์เดียวกัน

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

• สร้าง map เก็บความถี่ของแต่ละค่าในอาร์เรย์
• ใช้ map อีกชุดสำหรับเก็บคู่ที่นับแล้ว (ป้องกันซ้ำ)
• วนลูป i จาก 0 ถึง n-1, ลูป j จาก i+1 ถึง n-1
• ตรวจสอบว่าผลรวม arr[i]+arr[j] มีใน map ความถี่หรือไม่ และคู่นี้ยังไม่ถูกนับ
• เพิ่มตัวนับและบันทึกคู่ลง map ป้องกันซ้ำ

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

#include <iostream>
#include <map>
using namespace std;

int countPairs(int ar[], int n) {
    map freq;
    for (int i = 0; i < n; i++) freq[ar[i]]++;
    
    map, int> pairMap;
    int result = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int sum = ar[i] + ar[j];
            if (freq[sum] > 0 && pairMap[{ar[i], ar[j]}] == 0) {
                result++;
            }
            pairMap[{ar[i], ar[j]}]++;
            pairMap[{ar[j], ar[i]}]++;
        }
    }
    return result;
}

int main() {
    int ar[] = {6, 4, 10, 14};
    int n = sizeof(ar) / sizeof(ar[0]);
    cout << "count is " << countPairs(ar, n);
    return 0;
}

ผลลัพธ์

count is 2