【C++】指定された合計値となるすべてのペアを出力する方法

問題概要

この問題では、整数の配列と目標となる合計値が与えられ、その合計値と等しくなるすべての整数ペアを見つけて出力する必要があります。

具体例を使って問題を理解してみましょう。

入力： array = {1, 6, -2, 3}、sum = 4

出力： (1, 3) 、(6, -2)

つまり、指定された合計値を持つペアをすべて見つけ出すことが求められています。

解法1：ブルートフォース（全探索）

最もシンプルな解決策は、合計値を生成する要素のペアを一つずつ確認していく方法です。配列を走査し、各要素について合計値に一致する組み合わせとなる数を探すことで実装できます。

この方法は理解しやすい反面、二重ループを使用するため時間計算量がO(n²)となり、大きな配列に対しては非効率です。

サンプルプログラム

#include <iostream>
using namespace std;
int printPairsWithSum(int arr[], int n, int sum){
    int count = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (arr[i] + arr[j] == sum)
                cout<<"[ "<<arr[i]<<", "<<arr[j]<<" ]\n";
}
int main(){
    int arr[] = {1, 6, -2, 3};
    int n = 4;
    int sum = 4;
    cout<<"Pairs with Sum "<<sum<<" are :\n";
    printPairsWithSum(arr, n, sum);
    return 0;
}

出力結果

Pairs with Sum 4 are :
[ 1, 3 ]
[ 6, -2 ]

解法2：ハッシュテーブルを使った効率的な方法

上記の方法は簡単に理解できるものの、あまり効率的とは言えません。そこで有効なのがハッシュテーブルを活用するアプローチです。

手順は以下の通りです。

1. 空のハッシュテーブルを初期化する
2. 配列を順番に走査し、各要素に対して「合計値からその要素を引いた値（補完値）」を計算する
3. 補完値がすでにハッシュテーブルに存在すれば、それは合計値を持つペアなので出力する
4. 現在の要素をハッシュテーブルに登録して次へ進む

このアプローチにより、時間計算量をO(n)まで改善でき、大規模なデータでも高速に動作します。

サンプルプログラム

#include <bits/stdc++.h>
using namespace std;
void printPairsWithSum(int arr[], int n, int sum){
    unordered_map<int, int> pair;
    for (int i = 0; i < n; i++) {
        int rem = sum - arr[i];
        if (pair.find(rem) != pair.end()) {
            int count = pair[rem];
            for (int j = 0; j < count; j++)
                cout<<"["<<rem<<", "<<arr[i]<<" ]\n";
        }
        pair[arr[i]]++;
    }
}
int main(){
    int arr[] = {1, 6, -2, 3};
    int n = 4;
    int sum = 4;
    cout<<"The pair with sum is \n";
    printPairsWithSum(arr, n, sum);
    return 0;
}

出力結果

Pairs with Sum 4 are :
[ 1, 3 ]
[ 6, -2 ]

まとめ

指定された合計値を持つペアを見つけるには、全探索によるO(n²)の単純な方法と、ハッシュテーブルを用いたO(n)の効率的な方法の2つのアプローチがあります。小さな配列なら前者でも十分ですが、データサイズが大きい場合は後者のハッシュベースの手法を採用することで、大幅なパフォーマンス向上が期待できます。