查找具有給定總和的對，以便該對的元素位于不同的行中 · 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。