C++で合計が指定値xに等しくなる2つのソート済み配列のペアを数える方法

本記事では、正の整数を含む2つの配列と値 x が与えられたとき、1つ目の配列から要素 A、2つ目の配列から要素 B を選び、A + B = x となるペア (A, B) の個数を求める問題を扱います。

具体的な例で確認してみましょう。

入力例1

arr_1[] = {1, 2, 5, 3, 4}、arr_2[] = {7, 0, 1, 3}、x = 6

出力例1

合計が x に等しいペアの個数：2

説明： 条件を満たすペアは (5, 1)（arr_1[2] と arr_2[2]）および (3, 3)（arr_1[3] と arr_2[3]）です。

入力例2

arr_1[] = {1, 1, 1}、arr_2[] = {2, 2}、x = 6

出力例2

合計が x に等しいペアの個数：0

説明： どの組み合わせでも合計は最大3であり、6にはならないため該当するペアは存在しません。なお、x = 3 の場合は (1, 2) の組み合わせが複数回カウントされます。

アプローチ1：素朴な全探索（ナイーブ法）

最も基本的な方法は、二重の for ループによる全探索です。インデックス i で arr_1[] を、インデックス j で arr_2[] を走査し、arr_1[i] + arr_2[j] == x を満たすたびにカウントを増やします。計算量は O(n × m) となります。

• 正の要素を持つ整数配列 arr_1[] と arr_2[]、およびそれぞれの長さ size_arr_1、size_arr_2 を用意します。
• 関数 Pair_value_x(int arr_1[], int arr_2[], int size_arr_1, int size_arr_2, int x) が両方の配列とその長さを受け取り、合計が x になるペアの個数を返します。
• カウント変数 count の初期値を 0 とします。
• i = 0 から i < size_arr_1 まで、j = 0 から j < size_arr_2 まで二重ループで走査します。
• 各ペア (arr_1[i], arr_2[j]) について合計が x と等しければ count をインクリメントします。
• 最後に count を結果として返します。

アプローチ2：ハッシュセットを使った効率的な方法

より効率的な方法では、まず arr_1 の全要素を unordered_set に格納します。次に arr_2 をループで走査し、各値 arr_2[j] に対して「x − arr_2[j]」がセット内に存在するかを確認し、存在すればカウントを増やします。探索が O(1) で行えるため、全体の計算量は O(n + m) に改善できます。

• 同じく2つの配列とそのサイズを受け取ります。
• 関数 Pair_value_x(int arr_1[], int arr_2[], int size_arr_1, int size_arr_2, int x) が合計が x になるペアの個数を返します。
• カウント count の初期値を 0 とします。
• arr_1 の一意な要素を格納するため unordered_set<int> 型の hash_map を作成します。
• for ループで arr_1 の要素を hash_map に挿入します。
• 続いて for ループで arr_2[] を走査します。
• 各 arr_2[j] について、hash_map.find(x - arr_2[j]) != hash_map.end() が成立すれば count をインクリメントします。
• 最終的な count が合計 x となるペアの個数になります。
• count を結果として返します。

コード例（ナイーブ法）

#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;
}

出力

上記のコードを実行すると、次の出力が得られます。

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

コード例（効率的な方法）

#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;
}

出力

上記のコードを実行すると、次の出力が得られます。

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

まとめ

2つの配列から合計が x になるペアを数える問題は、単純な二重ループでは O(n × m) の時間がかかりますが、unordered_set を活用することで O(n + m) まで高速化できます。データ量が多い場合やパフォーマンスが重視される場面では、ハッシュセットを用いた効率的なアプローチを選択するのがおすすめです。