C++でa + b = c + dとなる4つの配列要素（a、b、c、d）を見つける方法

問題の概要

整数のリストが与えられたとき、(a, b) と (c, d) という2組のペアを構成する4つの異なる整数を見つけ、a + b = c + d が成り立つようにすることが課題です。条件を満たす答えが複数存在する場合は、そのうち1つだけを出力すれば十分です。

例えば、配列の要素が A = [7, 5, 9, 3, 6, 4, 2] の場合、(7, 3) と (6, 4) のようなペアが考えられます（どちらも合計は10）。

解法のアプローチ：ハッシュマップの活用

この問題はハッシュ（連想配列）のテクニックを使うことで効率的に解けます。ハッシュテーブルには、ペアの合計値をキーとして、対応するインデックスのペアを値として格納していきます。すべてのペアの合計を順番に調べ、同じ合計値が2回現れた時点で、条件を満たす2組のペアが見つかったことになります。

アルゴリズムの手順

• i を 0 から n − 1 まで繰り返します。
  • j を i + 1 から n − 1 まで繰り返します。
    • arr[i] と arr[j] の合計値を求めます。
    • ハッシュテーブルに同じ合計値が既に登録されている場合は、登録済みのペアと現在のペアを出力して終了します。
    • まだ存在しない場合は、現在のペアをハッシュテーブルに登録します。

このアルゴリズムの計算量は、すべてのペアを調べるため時間計算量 O(n²)、空間計算量も O(n²) となります。4重ループによる総当たり法（O(n⁴)）と比べて大幅な高速化が可能です。

C++での実装例

#include<iostream>
#include<map>
using namespace std;
bool getTwoPairs(int arr[], int n) {
    map<int, pair<int, int> > hash_table;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int sum = arr[i] + arr[j];
            if (hash_table.find(sum) == hash_table.end())
                hash_table[sum] = make_pair(i, j);
            else {
                pair<int, int> pp = hash_table[sum];
                cout << "(" << arr[pp.first] << " + " << arr[pp.second] << ") = (" << arr[i] << " + " << arr[j] << ")";
                return true;
            }
        }
    }
    cout << "No pairs found";
    return false;
}
int main() {
    int arr[] = {7, 5, 9, 3, 6, 4, 2};
    int n = sizeof arr / sizeof arr[0];
    cout << "The pairs are: ";
    getTwoPairs(arr, n);
}

実行結果

The pairs are: (7 + 4) = (5 + 6)

この出力では、(7 + 4) と (5 + 6) がどちらも11となり、a + b = c + d の条件を満たしていることが確認できます。条件を満たすペアが存在しない場合は、「No pairs found」と表示されます。