C++で2つの配列から合計がKに等しいユニークなペアを数える方法

この記事では、2つの整数配列 Arr1[] と Arr2[]、および目標値 K が与えられたときに、「Arr1[i] + Arr2[j] == K」を満たすユニークなペアの個数を求める方法を解説します。ペアは ( Arr1[i], Arr2[j] ) の形式で表されます。

基本的な考え方は、二重ループですべての組み合わせを走査し、合計が K に一致するペアを見つけたら、unordered_map を使って重複を排除しながらカウントしていくというものです。

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

入力例1

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

出力例1

合計がKに等しいペアの個数 : 4

説明

( Arr1[0], Arr2[4] ) → (1,3)
( Arr1[1], Arr2[2] ) → (3,1)
( Arr1[2], Arr2[1] ) → (2,2)
( Arr1[3], Arr2[2] ) → (3,1)

(3,1) は重複しているため1つとして数え、最終的なユニークなペアの総数は 4 となります。

入力例2

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

出力例2

合計がKに等しいペアの個数 : 1

説明

( Arr1[1], Arr2[0] ) → (2,1)

他のすべてのペアはすでに存在するため、ユニークなペアの総数は 1 です。

アルゴリズムの流れ

• 2つの配列 Arr1[]、Arr2[] と目標値 K を受け取ります。
• Len1 と Len2 はそれぞれの配列の長さを表します。
• 関数 pairsumisK(int arr1[], int arr2[], int k, int l1, int l2) がすべての引数を受け取り、合計が k となるユニークなペアの個数を返します。
• ペアを数えるための変数 count を 0 で初期化します。
• ユニークなペアを記録するために unordered_map を用意します。
• 二重の for ループで両方の配列を走査します。
• arr1[] の要素を i=0 から i<len1 まで、arr2[] の要素を j=0 から j<len2 まで調べます。
• arr1[i] + arr2[j] == k を満たすか確認し、満たす場合は umap.find(...) == umap.end() によってそのペアが未登録かどうかをチェックします。
• 未登録であれば、そのペアを umap に追加し、count をインクリメントします。
• すべてのループが終わった時点で、count には条件を満たすユニークなペアの総数が格納されています。
• count を結果として返します。

C++実装例

#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) // 合計がkに等しいペアのみ対象{
                if(umap.find(arr1[i]) == umap.end()) // ユニークなペアのみ{
                    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;
    cout << endl << "合計がKに等しいペアの個数 : " << pairsumisK(Arr1, Arr2, K, len1, len2);
    return 0;
}

出力

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

合計がKに等しいペアの個数 : 0

なお、元のコードでは count のインクリメントが抜けていたため、常に 0 が出力される不具合がありました。上記の実装例では umap.insert() の直後に count++ を追加することで、正しくユニークなペアの個数がカウントされるように修正しています。

計算量について

この手法の時間計算量は O(Len1 × Len2) であり、配列の長さが大きくなると処理時間が増加します。unordered_map による重複チェックは平均 O(1) で行えるため、全体として効率的ですが、より大規模な入力に対してはハッシュマップやソートを活用した最適化も検討できます。