查找具有给定总和的对，以便该对的元素位于不同的行中 · GeeksForGeeks 中文系列教程

# 查找具有给定总和的对，以便该对的元素位于不同的行中 > 原文： [https://www.geeksforgeeks.org/find-pairs-given-sum-elements-pair-different-rows/](https://www.geeksforgeeks.org/find-pairs-given-sum-elements-pair-different-rows/) 给定不同值和总和的矩阵。任务是找到给定总和等于给定总和的所有对。对中的每个元素必须来自不同的行，即；对不得位于同一行。 **示例**： ``` Input : mat[4][4] = {{1, 3, 2, 4}, {5, 8, 7, 6}, {9, 10, 13, 11}, {12, 0, 14, 15}} sum = 11 Output: (1, 10), (3, 8), (2, 9), (4, 7), (11, 0) ``` **方法 1（简单）** 解决此问题的简单方法是一个一个接一个地获取所有行的每个元素，并从矩阵中的下一行开始查找对。该方法的时间复杂度将为 O（n 4 ）。 **方法 2（使用排序）** * 按升序对所有行进行排序。该预处理的时间复杂度将为 O（n 2 logn）。 * 现在，我们将逐行选择每一行，并在当前行之后的其余行中找到对元素。 * 取两个迭代器**左**和**右**。 **左侧的**迭代器指向当前第 i 行的左角，**右侧的**迭代器指向下一个我们要在其中查找对元素的第 j 行的右角。 * 如果 **mat [i] [left] + mat [j] [right] <相加**，则**左++** ，即；向右移第 i 行，否则**向右++** ，即；在第 j 行向左角移动。 ## C++ ```cpp // C++ program to find a pair with given sum such that // every element of pair is in different rows. #include<bits/stdc++.h> using namespace std; const int MAX = 100; // Function to find pair for given sum in matrix // mat[][] --> given matrix // n --> order of matrix // sum --> given sum for which we need to find pair void pairSum(int mat[][MAX], int n, int sum) { // First sort all the rows in ascending order for (int i=0; i<n; i++) sort(mat[i], mat[i]+n); // Select i'th row and find pair for element in i'th // row in j'th row whose summation is equal to given sum for (int i=0; i<n-1; i++) { for (int j=i+1; j<n; j++) { int left = 0, right = n-1; while (left<n && right>=0) { if ((mat[i][left] + mat[j][right]) == sum) { cout << "(" << mat[i][left] << ", "<< mat[j][right] << "), "; left++; right--; } else { if ((mat[i][left] + mat[j][right]) < sum) left++; else right--; } } } } } // Driver program to run the case int main() { int n = 4, sum = 11; int mat[][MAX] = {{1, 3, 2, 4}, {5, 8, 7, 6}, {9, 10, 13, 11}, {12, 0, 14, 15}}; pairSum(mat, n, sum); return 0; } ``` ## Java ```java // Java program to find a pair with // given sum such that every element // of pair is in different rows. import java.util.Arrays; class GFG { static final int MAX = 100; // Function to find pair for given sum in // matrix mat[][] --> given matrix // n --> order of matrix // sum --> given sum for which we need to find pair static void pairSum(int mat[][], int n, int sum) { // First sort all the rows in ascending order for (int i = 0; i < n; i++) Arrays.sort(mat[i]); // Select i'th row and find pair for element in i'th // row in j'th row whose summation is equal to given sum for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { int left = 0, right = n - 1; while (left < n && right >= 0) { if ((mat[i][left] + mat[j][right]) == sum) { System.out.print("(" + mat[i][left] + ", " + mat[j][right] + "), "); left++; right--; } else { if ((mat[i][left] + mat[j][right]) < sum) left++; else right--; } } } } } // Driver code public static void main(String[] args) { int n = 4, sum = 11; int mat[] [] = {{1 , 3, 2, 4}, {5 , 8, 7, 6}, {9 , 10, 13, 11}, {12, 0, 14, 15}}; pairSum(mat, n, sum); } } // This code is contributed by Anant Agarwal. ``` ## Python 3 ``` # Python 3 program to find a pair with # given sum such that every element of # pair is in different rows. MAX = 100 # Function to find pair for given # sum in matrix mat[][] --> given matrix # n --> order of matrix # sum --> given sum for which we # need to find pair def pairSum(mat, n, sum): # First sort all the rows # in ascending order for i in range(n): mat[i].sort() # Select i'th row and find pair for # element in i'th row in j'th row # whose summation is equal to given sum for i in range(n - 1): for j in range(i + 1, n): left = 0 right = n - 1 while (left < n and right >= 0): if ((mat[i][left] + mat[j][right]) == sum): print( "(", mat[i][left], ", ", mat[j][right], "), ", end = " ") left += 1 right -= 1 else: if ((mat[i][left] + mat[j][right]) < sum): left += 1 else: right -= 1 # Driver Code if __name__ == "__main__": n = 4 sum = 11 mat = [[1, 3, 2, 4], [5, 8, 7, 6], [9, 10, 13, 11], [12, 0, 14, 15]] pairSum(mat, n, sum) # This code is contributed # by ChitraNayal ``` **输出**： ``` (1, 10), (3, 8), (2, 9), (4, 7), (11, 0) ``` **时间复杂度**： O（n 2 logn + n ^ 3） **辅助空间**：`O(1)` **方法 3（[散列](https://www.geeksforgeeks.org/hashing/)）** 1. 创建一个空的哈希表，并将 hash 中矩阵的所有元素存储为键，并将其位置存储为值。 2. 再次遍历矩阵以检查每个元素在散列表中是否存在。如果存在，则比较行号。如果行号不同，则打印该对。 ## CPP ``` // C++ program to find pairs with given sum such // the two elements of pairs are from different rows #include<bits/stdc++.h> using namespace std; const int MAX = 100; // Function to find pair for given sum in matrix // mat[][] --> given matrix // n --> order of matrix // sum --> given sum for which we need to find pair void pairSum(int mat[][MAX], int n, int sum) { // Create a hash and store all elements of matrix // as keys, and row and column numbers as values unordered_map<int, pair<int, int> > hm; for (int i=0; i<n; i++) for (int j=0; j<n; j++) hm[mat[i][j]] = make_pair(i, j); // Traverse the matrix again to check for every // element whether its pair exists or not. for (int i=0; i<n; i++) { for (int j=0; j<n; j++) { // Look for remaining sum in hash int remSum = sum - mat[i][j]; auto it = hm.find(remSum); // it is an iterator // of unordered_map type // If an element with value equal to remaining sum exists if (it != hm.end()) { // Find row and column numbers of element with // value equal to remaining sum. pair<int, int> p = it->second; int row = p.first, col = p.second; // If row number of pair is not same as current // row, then print it as part of result. // Second condition is there to make sure that a // pair is printed only once. if (row != i && row > i) cout << "(" << mat[i][j] << ", " << mat[row][col] << "), "; } } } } // Driver program int main() { int n = 4, sum = 11; int mat[][MAX]= {{1, 3, 2, 4}, {5, 8, 7, 6}, {9, 10, 13, 11}, {12, 0, 14, 15}}; pairSum(mat, n, sum); return 0; } ``` Output : ``` (1, 10), (3, 8), (2, 9), (4, 7), (11, 0), ``` 重要的是，当我们遍历一个矩阵时，一对可能会被打印两次。为了确保一对仅打印一次，我们检查从哈希表中选取的其他元素的行号是否大于当前元素的行号。时间复杂度：假设哈希表插入和搜索操作花费`O(1)`时间，则 `O(n^2)`。本文由 [**Shashank Mishra（Gullu）**](https://www.facebook.com/shashank.mishra.92167) 贡献。如果您喜欢 GeeksforGeeks 并希望做出贡献，则还可以使用 [tribution.geeksforgeeks.org](http://www.contribute.geeksforgeeks.org) 撰写文章，或将您的文章邮寄至 tribution@geeksforgeeks.org。查看您的文章出现在 GeeksforGeeks 主页上，并帮助其他 Geeks。