C++で配列内のab=cdとなるすべてのペア(a, b)と(c, d)を見つける方法

配列Aが与えられたとき、その中から積が等しくなる2つのペア(a, b)と(c, d)、つまりab = cdを満たす組み合わせを見つける問題を考えます。

例えば、配列A = [3, 4, 7, 1, 2, 9, 8]の場合、(4, 2)と(1, 8)というペアが条件を満たします。実際に4×2 = 8、1×8 = 8となり、積が一致していますね。

この問題を効率的に解くには、ハッシュテーブル（C++ではunordered_map）を活用します。すべてのペアの積を順に計算し、同じ積がすでにハッシュテーブルに登録されているかどうかを確認することで、条件を満たすペアを検出できます。

アルゴリズムの手順

1. iを0からn-1までループさせる
2. その内部でjをi+1からn-1までループさせる
3. 積 prod = arr[i] × arr[j] を計算する
4. prodがハッシュテーブルに存在しない場合、Hash[prod] = (i, j) として登録する
5. prodがすでに存在する場合、登録済みのペアと現在のペアを出力する

この方法により、全ペアを総当たりで比較するO(n⁴)の素朴な手法と比べて、大幅に効率化できます。

C++による実装例

#include <iostream>
#include <unordered_map>
using namespace std;

void displayPairs(int arr[], int n) {
    bool found = false;
    unordered_map<int, pair<int, int>> Hash;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int prod = arr[i] * arr[j];
            if (Hash.find(prod) == Hash.end())
                Hash[prod] = make_pair(i, j);
            else {
                pair<int, int> pp = Hash[prod];
                cout << "(" << arr[pp.first] << ", " << arr[pp.second]
                      << ") and (" << arr[i] << ", " << arr[j] << ")" << endl;
                found = true;
            }
        }
    }
    if (found == false)
        cout << "No pairs have Found" << endl;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
    int n = sizeof(arr) / sizeof(int);
    displayPairs(arr, n);
}

コードの解説

• unordered_map<int, pair<int, int>>：積（int）をキーとして、それを構成する要素のインデックスペア（pair<int, int>）を値として格納します。
• Hash.find(prod) == Hash.end()：同じ積がまだ登録されていないかを判定し、未登録なら新規登録します。
• foundフラグ：条件を満たすペアが1つも見つからなかった場合に、その旨を出力するために使用しています。

実行結果

(1, 6) and (2, 3)
(1, 8) and (2, 4)
(2, 6) and (3, 4)
(3, 8) and (4, 6)

出力を見ると、例えば(1, 6)と(2, 3)は1×6 = 6、2×3 = 6となり、確かにab = cdを満たしていることが確認できます。

計算量

• 時間計算量：O(n²) — すべてのペア(i, j)を一度ずつ調べるためです。
• 空間計算量：O(n²) — 最悪の場合、すべてのペアの積をハッシュテーブルに格納する必要があるためです。

このように、ハッシュテーブルを利用することで、積が一致するペアを効率的に検出できます。配列の要素数が大きくなっても、素朴な総当たり法よりはるかに実用的なアプローチです。