使用 C++ 在矩阵中找到给定总和的对

在本文中，我们将讨论在给定矩阵中找到具有给定和的对的程序。例如-

Input : matrix[n][m] = { { 4, 6, 4, 65 }, { 56, 1, 12, 32 }, { 4, 5, 6, 44 }, { 13, 9, 11, 25 } }, SUM = 20 Output : 对存在。 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 : 对不存在。 Explanation : No pair exists in the matrix whose sum is equal to 7.

寻找解决方案的方法

现在我们将解释两种不同的方法来找到上述问题的解决方案。

蛮力方法

考虑给定矩阵中的每一对，并检查该对的和是否等于给定的SUM，如果是，则打印“Pairexists”；否则，打印“Pairdoesnotexist”。应用这种方法非常简单，但它会将时间复杂度提高到O((N*M)2)。

有效的方法

该程序可以通过使用哈希存储所有矩阵元素然后遍历矩阵并检查[SUM&(indexelement)]的差值是否相等来提高效率。如果是，则打印“Exist”并退出程序。如果否，则遍历打印后，“不存在”。

示例

#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 << "对存在。" << endl; return 0; } else { hash.insert(matrix[i][j]); } } } cout << "对不存在。" << endl; return 0; }输出结果对不存在。

上面代码的解释

声明二维数组并在其中存储元素。

遍历数组找到if(sum-matrix[i][j])!=。hash.end()

如果条件满足，则打印“Pairexists”并从主函数返回。

否则，继续遍历数组，最后打印“Pairdoesnotexist”。

结论

在本文中，我们讨论了在矩阵或二维数组中找到具有给定总和的对；我们讨论了Brute-force方法和Efficient方法来解决这个问题。我们讨论了C++程序来解决这个问题。但是，我们可以使用任何其他语言（如C、Java、Python等）编写此程序。我们希望本文对您有所帮助。