C++で「ペアの合計値が配列内にすでに存在する」ペアを見つける方法

この記事では、N個の整数からなる配列 arr[] が与えられたとき、2つの要素の合計値がその配列内にすでに存在するようなペアを見つけるアルゴリズムを解説します。つまり、「ペアの合計値 = 配列内のいずれかの値」となる組み合わせをすべて抽出するのが目的です。

問題の理解：入力例と出力例

具体的な例を使って問題を確認しましょう。

入力

arr[] = {1, 2, 4, 6, 7}

出力

(1, 6), (2, 4)

説明

• ペア (1, 6) の場合：合計値は 7 であり、7 は配列内に存在します。
• ペア (2, 4) の場合：合計値は 6 であり、6 も配列内に存在します。

解法アプローチ1: 全探索（ブルートフォース）

最もシンプルな解決策は、配列の要素から作成できるすべてのペアを列挙する方法です。各ペアについて合計値を計算し、その値が配列内に存在するかどうかを線形探索で確認します。存在していれば、そのペアを出力します。

あわせて、見つかったペアの数を記録するカウンターを用意し、処理終了時にカウントが 0 であれば「該当するペアは見つかりませんでした」と表示するようにします。

この解法の動作を示すプログラムは以下の通りです。

実装例

#include <iostream>
using namespace std;
void findSumPairsArr(int arr[], int n){
    int pairCount = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = 0; k < n; k++) {
                if (arr[i] + arr[j] == arr[k]) {
                    cout<<"( "<<arr[i]<<", "<<arr[j]<<" ), sum = "<<(arr[i] + arr[j])<<"\n";
                    pairCount++;
                }
            }
        }
    }
    if (!pairCount)
        cout<<"No Such Pairs found !";
}
int main() {
    int arr[] = { 1, 2, 4, 6, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"Pairs in array whose sum already exists in array : \n";
    findSumPairsArr(arr, n);
    return 0;
}

出力

配列内で合計値がすでに存在するペア −

( 1, 6 ), sum = 7
( 2, 4 ), sum = 6

この方法では、ペアの生成に2重ループ、さらに合計値の探索にもループが必要なため、時間計算量は O(N³) となります。データサイズが大きくなると非効率になる点に注意しましょう。

解法アプローチ2: ハッシュテーブルを使った効率的な解法

より効果的なアプローチとして、ハッシュテーブルを活用する方法があります。まず配列のすべての要素をハッシュテーブルに挿入しておきます。その後、すべてのペアをチェックして合計値を計算し、その値がハッシュテーブルに存在するかどうかを平均 O(1) の時間で確認できます。

C++ では、STL の unordered_set を使うことでハッシュテーブルを簡単に実装できます。こちらも同様に、見つかったペアの数をカウントし、pairCount が 0 の場合は「No Such Pairs found !」と表示します。

実装例

#include <bits/stdc++.h>
using namespace std;
void findSumPairsArr(int arr[], int n) {
    unordered_set<int> HT;
    for (int i = 0; i < n; i++)
        HT.insert(arr[i]);
    int pairCount = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (HT.find(arr[i] + arr[j]) != HT.end()) {
                cout<<"( "<<arr[i]<<", "<<arr[j]<<" ), sum = "
                    <<(arr[i] + arr[j])<<"\n";
                pairCount++;
            }
        }
    }
    if (!pairCount)
        cout<<"No Such Pairs found !";
}
int main() {
    int arr[] = {1, 2, 4, 6, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"Pairs in array whose sum already exists in array : \n";
    findSumPairsArr(arr, n);
    return 0;
}

出力

配列内で合計値がすでに存在するペア −

( 1, 6 ), sum = 7
( 2, 4 ), sum = 6

まとめ

ハッシュテーブルを利用することで、合計値の存在確認が高速化され、全体の時間計算量を O(N³) から O(N²) まで改善できます。メモリを追加で消費する代わりに大幅な高速化が得られるため、実務的には unordered_set を使った手法が推奨されます。