C++で行列内から指定した合計値となるペアを検索する方法

本記事では、与えられた行列（2次元配列）の中から、指定された合計値（SUM）と等しくなる要素のペアを検索するプログラムについて解説します。まずは具体的な例を見てみましょう。

入力 : matrix[n][m] = { 
    { 4, 6, 4, 65 }, 
    { 56, 1, 12, 32 },
    { 4, 5, 6, 44 },
    { 13, 9, 11, 25 } 
}, SUM = 20

出力 : ペアが存在します。
説明 : 行列内に存在する 9 と 11 の合計が 20 となり、条件を満たすためです。

入力 : matrix[n][m] = { 
    { 5, 7, 3, 45 },  
    { 63, 5, 3, 7 },  
    { 11, 6, 9, 5 },
    { 8, 6, 14, 15 } 
}, SUM = 13
出力 : ペアが存在しません。
説明 : 合計が 13 となる要素のペアは行列内に存在しません。

解決策へのアプローチ

この問題を解くためのアプローチとして、ここでは2つの異なる方法を紹介します。

1. 総当たり（ブルートフォース）アプローチ

最もシンプルな方法は、行列内のすべての要素ペアを順番に調べ、その合計が指定された SUM と一致するかどうかを確認することです。一致するペアが見つかれば「ペアが存在します」と出力し、見つからなければ「ペアが存在しません」と出力します。

このアプローチは実装が非常に簡単ですが、すべてのペアを調べる必要があるため、時間計算量は O((N×M)²) まで増加してしまいます。行列のサイズが大きくなると非効率になる点に注意が必要です。

2. 効率的なアプローチ（ハッシュを活用）

より効率的に解くには、ハッシュセットを利用します。手順は以下の通りです。

• 行列の各要素を走査しながらハッシュセットに格納していく。
• 各要素に対して「SUM − 現在の要素」の値がすでにハッシュセット内に存在するかどうかを確認する。
• 存在すれば「ペアが存在します」と出力してプログラムを終了する。
• 最後まで見つからなければ、「ペアが存在しません」と出力する。

この方法では、ハッシュセットへの挿入・検索が平均 O(1) で行えるため、全体の時間計算量を O(N×M) に抑えられます。

C++による実装例

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

#define n 4
#define m 4

int main() {
    int matrix[n][m] = { 
        { 5, 7, 3, 45 },
        { 63, 5, 3, 7 },
        { 11, 6, 9, 5 },
        { 8, 6, 14, 15 } 
    };

    int sum = 7;
    unordered_set<int> hash;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (hash.find(sum - matrix[i][j]) != hash.end()) {
                cout << "Pair exists." << endl;
                return 0;
            } else {
                hash.insert(matrix[i][j]);
            }
        }
    }

    cout << "Pair does not exist." << endl;
    return 0;
}

出力結果

Pair does not exist.

コードの解説

• まず2次元配列を宣言し、要素を格納します。
• 配列を走査しながら、(sum - matrix[i][j]) の値がハッシュセット内に存在するかどうかを hash.find() で確認します。
• 条件を満たす場合、「Pair exists.」と出力し、main 関数から即座に return します。
• 条件を満たさない場合は、現在の要素をハッシュセットに追加して走査を続けます。
• 最後までペアが見つからなければ、「Pair does not exist.」を出力して終了します。

まとめ

本記事では、行列（2次元配列）の中から指定された合計値となるペアを検索する方法について解説しました。総当たり法とハッシュを用いた効率的な手法の2つのアプローチを取り上げ、C++での実装例も紹介しました。なお、このアルゴリズムはC言語やJava、Pythonなど他のプログラミング言語でも同様に実装可能です。本記事が皆さんの学習の一助になれば幸いです。