Đếm cặp từ hai mảng có tổng bằng K trong C++

Cho hai mảng Arr1[] và Arr2[] và một số K. Mục tiêu là tìm các cặp duy nhất các phần tử của hai mảng sao cho tổng của chúng bằng K. Cặp sẽ có dạng (Arr1[i], Arr2[j]) với Arr1[i] + Arr2[j] == K.

Ta duyệt bằng hai vòng lặp cho i và j. Nếu tổng (Arr1[i] + Arr2[j]) == K. Và cặp không tồn tại trong unordered_map<int,int>. Thêm vào map và tăng count.

Hãy hiểu qua các ví dụ.

Đầu vào

Arr1[]={ 1,3,2,4,3,2 }; Arr2[]={ 0,2,1,2,3 }; K=4

Đầu ra

Số cặp có tổng K: 4

Giải thích

Các cặp: (Arr1[0], Arr2[4]) → (1,3), (Arr1[1], Arr2[2]) → (3,1), (Arr1[2], Arr2[1]) → (2,2), (Arr1[3], Arr2[2]) → (3,1). Các cặp khác đã tồn tại. Tổng cặp duy nhất: 4.

Đầu vào

Arr1[]={ 0,2,1,2,3 }; Arr2[]={ 1,1,1,1,1 }; K=3

Đầu ra

Số cặp có tổng K: 1

Giải thích

Cặp: (Arr1[1], Arr2[0]) → (2,1). Các cặp khác đã tồn tại. Tổng cặp duy nhất: 1.

Phương pháp sử dụng trong chương trình dưới đây

• Nhận hai mảng Arr1[], Arr2[] và biến K cho tổng.
• Len1 và Len2 biểu thị độ dài hai mảng.
• Hàm pairsumisK(int arr1[], int arr2[], int k, int l1, int l2) nhận tất cả biến và trả về số cặp duy nhất từ hai mảng có tổng = k.
• Khởi tạo biến count = 0 cho cặp.
• Dùng unordered_map umap để lưu cặp duy nhất.
• Duyệt cả hai mảng bằng hai vòng lặp for.
• Với phần tử arr1[] từ i=0 đến i<len1. Với phần tử arr2[] từ j=0 đến j<len2.
• Kiểm tra nếu tổng arr1[i] + arr2[j] = k. Nếu có, kiểm tra cặp này tồn tại qua umap.find(...) == umap.end().
• Nếu chưa có, thêm cặp vào umap và tăng count.
• Sau tất cả vòng lặp count chứa tổng số cặp như vậy.
• Trả về count làm kết quả.

Ví dụ

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

int pairsumisK(int arr1[], int arr2[], int k, int l1, int l2) {
    int count = 0;
    unordered_map<int, int> umap;
    for (int i = 0; i < l1; i++) {
        for (int j = 0; j < l2; j++) {
            int sum = arr1[i] + arr2[j];
            if(sum == k) { // chỉ cặp có tổng = k
                if(umap.find(arr1[i]) == umap.end()) { // chỉ cặp duy nhất
                    umap.insert(make_pair(arr1[i], arr2[j]));
                    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; // độ dài mảng
    cout << endl << "Số cặp có tổng K: " << pairsumisK(Arr1, Arr2, K, len1, len2);
    return 0;
}

Đầu ra

Nếu chạy mã trên sẽ cho kết quả sau:

Số cặp có tổng K: 0