Đếm số cặp khác nhau có tổng tồn tại trong mảng trong C++

Cho một mảng số nguyên arr[], nhiệm vụ là đếm số cặp khác nhau (distinct pairs) trong mảng mà tổng của cặp đó cũng tồn tại trong chính mảng đó.

Lưu ý quan trọng

• Cặp (a,b) và (b,a) được coi là một cặp duy nhất
• Nếu một số xuất hiện nhiều lần, chỉ được dùng tối đa 2 lần để tạo một cặp (ví dụ: {2,2,2,2} chỉ tạo được 1 cặp (2,2))

Ví dụ

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

Giải thích - Các cặp có tổng trong mảng: (6,4) tổng=10, (10,4) tổng=14.

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

Phương pháp tiếp cận

• Dùng map để lưu tần suất xuất hiện của từng phần tử
• Duyệt qua tất cả các cặp (i,j) với i < j
• Kiểm tra xem tổng arr[i]+arr[j] có tồn tại trong map không
• Dùng map của cặp để tránh đếm trùng lặp
• Tăng count khi tìm thấy cặp hợp lệ

Ví dụ code C++

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

int countpairs(int ar[], int n) {
    map<int, int> mymap;
    for (int i = 0; i < n; i++)
        mymap[ar[i]]++;

    map<pair<int, int>, int> p;
    int result = 0;

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (mymap[ar[i] + ar[j]] > 0 && p[{ar[i], ar[j]}] == 0) {
                result++;
            }
            p[{ar[i], ar[j]}]++;
            p[{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;
}

Kết quả

count is 2