找到具有给定和的对，使对中的元素位于不同的行中-yiteyi-C++库

给定一个由不同值和一个和组成的矩阵。任务是找到给定矩阵中的所有对，其和等于给定的和。一对中的每个元素必须来自不同的行，即：；两人不能躺在同一排。

null

例如：

Input : mat[4][4] = {{1, 3, 2, 4},                     {5, 8, 7, 6},                     {9, 10, 13, 11},                     {12, 0, 14, 15}}        sum = 11Output: (1, 10), (3, 8), (2, 9), (4, 7), (11, 0)

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

方法1（简单） 这个问题的一个简单解决方案是，一个接一个地取所有行的每个元素，并从矩阵中的下一个直接行开始寻找对。这个 时间复杂性 因为这种方法是O（n ^4. ). 方法2（使用排序） 在内部

按升序对所有行进行排序。这个 时间复杂性 因为这个预处理将是O（n ^2. logn）。
现在我们将逐个选择每一行，并在当前行之后的其余行中找到pair元素。
以两个迭代器为例，左边和正当 . 左边迭代器指向当前第i行的左角正当迭代器指向下一个第j行的右角，我们将在其中找到一对元素。
如果 mat[i][left]+mat[j][right] 然后 左++ 即；在第一排向右转，否则 对++ 即；在第j排向左转。

C++

                         // 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 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                       

C#

                         // C# program to find a pair with                       
                         // given sum such that every element                       
                         // of pair is in different rows.                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         public                                     class                                     GFG {                       
           
                         // 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++)                       
                                                 {                       
                                                 List<                                     int                                     > l =                                     new                                     List<                                     int                                     >();                       
                                                 for                                     (                                     int                                     j = 0; j<n;j++)                       
                                                 {                       
                                                 l.Add(mat[i,j]);                       
                                                 }                       
                                                 l.Sort();                       
                                   
                                                 for                                     (                                     int                                     j = 0; j<n;j++)                       
                                                 {                       
                                                 mat[i,j] = l[j];                       
                                                 }                       
                                                 }                       
           
                                                 // 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) {                       
                                                 Console.Write(                                     "("                                     + 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 rutvik_56.                       

Javascript

                         <script>                       
           
                         // Javascript program to find a pair with                       
                         // given sum such that every element                       
                         // of pair is in different rows.                       
           
                         let 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                       
                         function                                     pairSum(mat, n, sum) {                       
                                   
                                                 // First sort all the rows in ascending order                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 mat[i].sort((a, b) => a - b);                       
                                   
                                                 // 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                                     (let i = 0; i < n - 1; i++) {                       
                                                 for                                     (let j = i + 1; j < n; j++) {                       
                                                 let left = 0, right = n - 1;                       
                                                 while                                     (left < n && right >= 0) {                       
                                                 if                                     ((mat[i][left] + mat[j][right]) == sum) {                       
                                                 document.write(                                     "("                                     + mat[i][left] +                                     ", "                                     +                       
                                                 mat[j][right] +                                     "), "                                     );                       
                                                 left++;                       
                                                 right--;                       
                                                 }                       
                                                 else                                     {                       
                                                 if                                     ((mat[i][left] + mat[j][right]) < sum)                       
                                                 left++;                       
                                                 else                       
                                                 right--;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Driver program                       
           
                                                 let n = 4, sum = 11;                       
                                                 let mat = [[1 ,  3,  2,  4],                       
                                                 [5 ,  8,  7,  6],                       
                                                 [9 , 10, 13, 11],                       
                                                 [12,  0, 14, 15]];                       
                                   
                                                 pairSum(mat, n, sum);                       
                                   
                         </script>                       

输出：

(1, 10), (3, 8), (2, 9), (4, 7), (11, 0)

时间复杂性： O（n） ^2. logn+n^3） 辅助空间： O（1）

方法3( 散列 )

创建一个空哈希表，将哈希表中矩阵的所有元素作为键存储，并将它们的位置作为值存储。
再次遍历矩阵，检查每个元素的对是否存在于哈希表中。如果存在，则比较行号。如果行号不相同，则打印一对。

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 as values                       
                                                 unordered_map<                                     int                                     ,                                     int                                     > hm;                       
           
                                                 // Traverse the matrix 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 numbers of element with                       
                                                 // value equal to remaining sum.                       
                                                 int                                     row = hm[remSum];                       
           
                                                 // 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)                       
                                                 cout <<                                     "("                                     << mat[i][j] <<                                     ", "                       
                                                 << remSum <<                                     "), "                                     ;                       
                                                 }                       
                                                 hm[mat[i][j]] = i;                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // 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;                       
                         }                       

JAVA

                         // Java program to find pairs with given sum such                       
                         // the two elements of pairs are from different rows                       
                         import                                     java.io.*;                       
                         import                                     java.util.*;                       
                         class                                     GFG                       
                         {                       
           
                                                 static                                     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)                       
                                                 {                       
           
                                                 // Create a hash and store all elements of matrix                       
                                                 // as keys, and row and column numbers as values                       
                                                 Map<Integer,ArrayList<Integer>> hm =                                     new                                     HashMap<Integer, ArrayList<Integer>>();                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j =                                     0                                     ; j < n; j++)                       
                                                 {                       
                                                 hm.put(mat[i][j],                                     new                                     ArrayList<Integer>(Arrays.asList(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];                       
           
                                                 // If an element with value equal to remaining sum exists                       
                                                 if                                     (hm.containsKey(remSum))                       
                                                 {                       
           
                                                 // Find row and column numbers of element with                       
                                                 // value equal to remaining sum.                       
                                                 ArrayList<Integer> p = hm.get(remSum);                       
                                                 int                                     row = p.get(                                     0                                     ), col = p.get(                                     1                                     );                       
           
                                                 // 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)                       
                                                 {                       
                                                 System.out.print(                                     "("                                     + mat[i][j] +                                     ","                                     + mat[row][col] +                                     "), "                                     );                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // 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 avanitrachhadiya2155                       

Python3

                         # JavaScript program to find pairs with given sum such                       
                         # the two elements of pairs are from 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                                     ):                       
                                   
                                                 # Create a hash and store all elements of matrix                       
                                                 # as keys, and row and column numbers as values                       
                                                 hm                                     =                                     {}                       
                                   
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 for                                     j                                     in                                     range                                     (n):                       
                                                 hm[mat[i][j]]                                     =                                     [i, j]                       
                                   
                                                 # Traverse the matrix again to check for every                       
                                                 # element whether its pair exists or not.                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 for                                     j                                     in                                     range                                     (n):                       
                                   
                                                 # Look for remaining sum in hash                       
                                                 remSum                                     =                                     sum                                     -                                     mat[i][j]                       
                                   
                                                 # If an element with value equal to remaining sum exists                       
                                                 if                                     remSum                                     in                                     hm:                       
                                   
                                                 # Find row and column numbers of element with                       
                                                 # value equal to remaining sum.                       
                                                 p                                     =                                     hm[remSum]                       
                                                 row                                     =                                     p[                                     0                                     ]                       
                                                 col                                     =                                     p[                                     1                                     ]                       
                                   
                                                 # 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                                     and                                     row > i):                       
                                                 print                                     (                                     "("                                     , mat[i][j] ,                                     ","                                     , mat[row][col] ,                                     "), "                                     , end                                     =                                     "")                       
                                   
                         # Driver code                       
                         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 patel2127                       

C#

                         // C# program to find pairs with given sum such                       
                         // the two elements of pairs are from different rows                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
                         public                                     class                                     GFG                       
                         {                       
           
                                                 // 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)                       
                                                 {                       
           
                                                 // Create a hash and store all elements of matrix                       
                                                 // as keys, and row and column numbers as values                       
                                                 Dictionary<                                     int                                     ,List<                                     int                                     >> hm =                                     new                                     Dictionary<                                     int                                     ,List<                                     int                                     >>();                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j = 0; j < n; j++)                       
                                                 {                       
                                                 hm.Add(mat[i,j],                                     new                                     List<                                     int                                     >(){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];                       
           
                                                 // If an element with value equal to remaining sum exists                       
                                                 if                                     (hm.ContainsKey(remSum))                       
                                                 {                       
           
                                                 // Find row and column numbers of element with                       
                                                 // value equal to remaining sum.                       
                                                 List<                                     int                                     > p = hm[remSum];                       
                                                 int                                     row = p[0], col = p[1];                       
           
                                                 // 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)                       
                                                 {                       
                                                 Console.Write(                                     "("                                     + mat[i, j] +                                     ","                                     + mat[row, col] +                                     "), "                                     );                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // Driver code                       
                                                 static                                     public                                     void                                     Main (){                       
                                                 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 rag2127                       

Javascript

                         <script>                       
           
                         // JavaScript program to find pairs with given sum such                       
                         // the two elements of pairs are from different rows                       
           
                         let 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                       
                         function                                     pairSum(mat,n,sum)                       
                         {                       
                                                 // Create a hash and store all elements of matrix                       
                                                 // as keys, and row and column numbers as values                       
                                                 let hm =                                     new                                     Map();                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 {                       
                                                 for                                     (let j = 0; j < n; j++)                       
                                                 {                       
                                                 hm.set(mat[i][j], [i, j] );                       
                                                 }                       
                                   
                                                 }                       
                                   
                                                 // Traverse the matrix again to check for every                       
                                                 // element whether its pair exists or not.                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 {                       
                                                 for                                     (let j = 0; j < n; j++)                       
                                                 {                       
                                   
                                                 // Look for remaining sum in hash                       
                                                 let remSum = sum - mat[i][j];                       
                                   
                                                 // If an element with value equal to remaining sum exists                       
                                                 if                                     (hm.has(remSum))                       
                                                 {                       
                                   
                                                 // Find row and column numbers of element with                       
                                                 // value equal to remaining sum.                       
                                                 let p = hm.get(remSum);                       
                                                 let row = p[0], col = p[1];                       
                                   
                                                 // 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)                       
                                                 {                       
                                                 document.write(                                     "("                                     + mat[i][j] +                                     ","                                     +                       
                                                 mat[row][col] +                                     "), "                                     );                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         let n = 4, sum = 11;                       
                         let 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 ab2127                       
           
                         </script>                       

输出：

(1, 10), (3, 8), (2, 9), (4, 7), (11, 0),

一件重要的事情是，当我们遍历一个矩阵时，一对可能被打印两次。为了确保一对只打印一次，我们检查从哈希表中选取的其他元素的行号是否大于当前元素的行号。 时间复杂性： O（n） ^2. )假设哈希表插入和搜索操作需要O（1）个时间。

本文由 沙申克·米什拉（古卢） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章