C++で合計が等しいペアを未ソート配列からすべて出力する方法

問題の概要

本記事では、ソートされていない配列の中から、合計値が等しくなるすべてのペアを見つけ出して出力する方法を、C++のコード例とともに解説します。

具体例で理解する

まず、簡単な例で問題を確認しましょう。

入力: array = [12, 13, 20, 5]
出力: [12, 13] と [20, 5] ―― どちらも合計は 25

このように、異なる要素同士の組み合わせであっても、合計値が一致するペアをすべて見つけるのが目的です。

解決のアプローチ

この問題を解くための基本的な流れは以下の通りです。

1. 配列内のすべてのペア (i, j) を二重ループで列挙し、それぞれの合計値を求めます。
2. 重複したペアの出力を避けるため、map（連想配列）を利用して「合計値 → ペアのリスト」という形でグループ化します。
3. 最後にマップを走査し、同じ合計値を持つペアが複数登録されているグループだけを順に出力します。

ポイントは、mapのキーに合計値、値に pair 型の vector を格納することです。これにより、同じ合計値を持つペアが自動的にまとめられ、重複チェックも容易になります。

C++による実装例

上記のロジックを実装したプログラムがこちらです。

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

// 合計が等しいペアを検索して出力する関数
void findEqualSumPairs(int A[], int n){
    // キー: 合計値 / 値: ペア(int, int)のvector
    map<int, vector<pair<int, int> > > map1;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            pair<int, int> p = make_pair(A[i], A[j]);
            map1[A[i] + A[j]].push_back(p);
        }
    }
    // 同じ合計値を持つペアが複数あるグループのみ出力
    for (auto value = map1.begin(); value != map1.end(); value++) {
        if (value->second.size() > 1) {
            for (int i = 0; i < value->second.size(); i++) {
                cout << "[ " << value->second[i].first << ", " << value->second[i].second << "] ";
            }
            cout << "have sum : " << value->first << endl;
        }
    }
}
int main() {
    int A[] = { 6, 4, 12, 10, 22, 11, 8, 2 };
    int n = sizeof(A) / sizeof(A[0]);
    cout << "Pairs with same sum are : \n";
    findEqualSumPairs(A, n);
    return 0;
}

実行結果

Pairs with same sum are :
[ 6, 4] [ 8, 2] have sum : 10
[ 4, 8] [ 10, 2] have sum : 12
[ 6, 8] [ 4, 10] [ 12, 2] have sum : 14
[ 6, 10] [ 4, 12] have sum : 16
[ 6, 12] [ 10, 8] have sum : 18

たとえば最初の行では、「6 + 4 = 10」「8 + 2 = 10」となり、合計が10になる2組のペアが出力されています。このように、合計値ごとにペアがグループ化されて表示されるのがわかります。

計算量について

すべてのペアを列挙するため、時間計算量は O(n²) です。また、ペアをマップに保存するため、空間計算量も最大で O(n²) となります。小〜中規模の配列であれば十分実用的ですが、大規模なデータを扱う場合はパフォーマンスに注意が必要です。

まとめ

未ソート配列から合計が等しいペアをすべて見つけるには、mapを使って合計値ごとにペアをグループ化するのが効果的です。二重ループで全ペアを走査し、mapへの登録と出力時のフィルタリングだけで、シンプルかつ正確に実装できます。