Đếm cặp từ hai mảng đã sắp xếp có tổng bằng x trong C++

Cho hai mảng số dương và giá trị x. Tìm số cặp (A,B) với A từ mảng 1, B từ mảng 2 sao cho A+B=x.

Ví dụ

Đầu vào − arr_1[] = {1,2,5,3,4}, arr_2[] = {7,0,1,3}, x=6

Đầu ra − 2

Giải thích − (5,1) và (3,3).

Đầu vào − arr_1[] = {1,1,1}, arr_2[] = {2,2}, x=6

Đầu ra − 2

Giải thích − (1,2) từ chỉ số (0,0) và (1,1).

Phương pháp giải

Cách 1 (naive): 2 vòng lặp, kiểm tra arr_1[i] + arr_2[j] == x.

Cách 2 (hiệu quả): Tạo unordered_set từ arr_1. Duyệt arr_2, nếu x - arr_2[j] có trong set thì count++.

• Cách 1: lặp 2 vòng, đếm trực tiếp.
• Cách 2: unordered_set hash_map chứa phần tử arr_1. Duyệt arr_2, kiểm tra hash_map.find(x - arr_2[j]) != end().

Ví dụ code (naive)

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

int Pair_value_x(int arr_1[], int arr_2[], int size_arr_1, int size_arr_2, int x) {
    int count = 0;
    for (int i = 0; i < size_arr_1; i++)
        for (int j = 0; j < size_arr_2; j++)
            if (arr_1[i] + arr_2[j] == x) count++;
    return count;
}

int main() {
    int arr_1[] = {1, 2, 3, 4};
    int arr_2[] = {2, 3, 4, 5};
    int size_arr_1 = sizeof(arr_1) / sizeof(arr_1[0]);
    int size_arr_2 = sizeof(arr_2) / sizeof(arr_2[0]);
    int x = 6;
    cout << "Count of pairs from two sorted arrays whose sum is equal to a given value x are: " << Pair_value_x(arr_1, arr_2, size_arr_1, size_arr_2, x);
    return 0;
}

Đầu ra

Count of pairs from two sorted arrays whose sum is equal to a given value x are: 4

Ví dụ code (hiệu quả)

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

int Pair_value_x(int arr_1[], int arr_2[], int size_arr_1, int size_arr_2, int x) {
    int count = 0;
    unordered_set<int> hash_map;
    for (int i = 0; i < size_arr_1; i++) hash_map.insert(arr_1[i]);
    for (int j = 0; j < size_arr_2; j++)
        if (hash_map.find(x - arr_2[j]) != hash_map.end()) count++;
    return count;
}

int main() {
    int arr_1[] = {1, 2, 3, 4};
    int arr_2[] = {2, 3, 4, 5};
    int size_arr_1 = sizeof(arr_1) / sizeof(arr_1[0]);
    int size_arr_2 = sizeof(arr_2) / sizeof(arr_2[0]);
    int x = 6;
    cout << "Count of pairs from two sorted arrays whose sum is equal to a given value x are: " << Pair_value_x(arr_1, arr_2, size_arr_1, size_arr_2, x);
    return 0;
}

Đầu ra

Count of pairs from two sorted arrays whose sum is equal to a given value x are: 4