C ++を使用して、行列内の指定された合計を持つペアを検索します

この記事では、与えられた行列で与えられた合計を持つペアを見つけるプログラムについて説明します。例-

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

Output : Pair exists.
Explanation : Sum = 20 is equal to the sum of numbers 9 and 11 which exists in the matrix.

Input : matrix[n][m] = { 
   { 5, 7, 3, 45 },  
   { 63, 5, 3, 7 },  
   { 11, 6, 9, 5 },
   { 8, 6, 14, 15 } 
}, SUM = 13
Output : Pair does not exist.
Explanation : No pair exists in the matrix whose sum is equal to 7.

解決策を見つけるためのアプローチ

次に、上記の問題の解決策を見つけるための2つの異なるアプローチについて説明します。

ブルートフォースアプローチ

指定された行列の各ペアを検討し、ペアの合計が指定されたSUMと等しいかどうかを確認します。等しい場合は、「ペアが存在します」と出力します。それ以外の場合は、「ペアは存在しません」と印刷します。このアプローチの適用は非常に簡単ですが、時間計算量がO（（N * M）2）になります。

効率的なアプローチ

このプログラムは、ハッシュを使用してすべての行列要素を格納し、行列をトラバースして、[SUM＆（インデックス要素）]の差が等しいかどうかを確認することで効率的になります。はいの場合は、「存在する」と印刷してプログラムを終了します。 NOの場合、印刷をトラバースした後、「存在しません」。

例

#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次元配列を宣言して要素を格納します。
• 配列をトラバースしてif（sum --matrix [i] [j]）！=hash.end（）。
• 条件が満たされている場合は、「ペアが存在します」と印刷して、メイン機能から戻ります。
• それ以外の場合は、アレイをトラバースし続け、最後に「ペアが存在しません」と出力します。

結論

この記事では、行列または2次元配列で特定の合計を持つペアを見つける方法について説明しました。この問題を解決するためのブルートフォースアプローチと効率的なアプローチについて説明しました。この問題を解決するためのC++プログラムについて説明しました。ただし、このプログラムはC、Java、Pythonなどの他の言語で作成できます。この記事がお役に立てば幸いです。