给定一个不同整数的数组，找出是否有两对（a，b）和（c，d），这样a+b=c+d，a，b，c和d是不同的元素。如果有多个答案，请打印其中任何一个。
null
例子：
Input: {3, 4, 7, 1, 2, 9, 8}Output: (3, 8) and (4, 7)Explanation: 3+8 = 4+7Input: {3, 4, 7, 1, 12, 9};Output: (4, 12) and (7, 9)Explanation: 4+12 = 7+9Input: {65, 30, 7, 90, 1, 9, 8};Output: No pairs found
预期时间复杂度： O（n） 2. )
A. 简单解决方案 就是运行四个循环来生成所有可能的四倍数组元素。对于每四个（a，b，c，d），检查（a+b）=（c+d）。该解的时间复杂度为O（n） 4. ). 一 有效解决方案 可以用O（n）来解决这个问题 2. )时间到了。这个想法是使用 散列 .我们在哈希表中使用sum作为键，pair作为值。
Loop i = 0 to n-1 : Loop j = i + 1 to n-1 : calculate sum If in hash table any index already exist Then print (i, j) and previous pair from hash table Else update hash table EndLoop;EndLoop;
下面是上述想法的实现。在下面的实现中，使用映射而不是哈希。地图插入和搜索的时间复杂度实际上是O（logn），而不是O（1）。下面是O（n） 2. 日志n）。
C++
// Find four different elements a,b,c and d of array such that // a+b = c+d #include<bits/stdc++.h> using namespace std; bool findPairs( int arr[], int n) { // Create an empty Hash to store mapping from sum to // pair indexes map< int , pair< int , int > > Hash; // Traverse through all possible pairs of arr[] for ( int i = 0; i < n; ++i) { for ( int j = i + 1; j < n; ++j) { // If sum of current pair is not in hash, // then store it and continue to next pair int sum = arr[i] + arr[j]; if (Hash.find(sum) == Hash.end()) Hash[sum] = make_pair(i, j); else // Else (Sum already present in hash) { // Find previous pair pair< int , int > pp = Hash[sum]; // pp->previous pair // Since array elements are distinct, we don't // need to check if any element is common among pairs cout << "(" << arr[pp.first] << ", " << arr[pp.second] << ") and (" << arr[i] << ", " << arr[j] << ")n" ; return true ; } } } cout << "No pairs found" ; return false ; } // Driver program int main() { int arr[] = {3, 4, 7, 1, 2, 9, 8}; int n = sizeof arr / sizeof arr[0]; findPairs(arr, n); return 0; } |
JAVA
// Java Program to find four different elements a,b,c and d of // array such that a+b = c+d import java.io.*; import java.util.*; class ArrayElements { // Class to represent a pair class pair { int first, second; pair( int f, int s) { first = f; second = s; } }; boolean findPairs( int arr[]) { // Create an empty Hash to store mapping from sum to // pair indexes HashMap<Integer,pair> map = new HashMap<Integer,pair>(); int n=arr.length; // Traverse through all possible pairs of arr[] for ( int i= 0 ; i<n; ++i) { for ( int j=i+ 1 ; j<n; ++j) { // If sum of current pair is not in hash, // then store it and continue to next pair int sum = arr[i]+arr[j]; if (!map.containsKey(sum)) map.put(sum, new pair(i,j)); else // Else (Sum already present in hash) { // Find previous pair pair p = map.get(sum); // Since array elements are distinct, we don't // need to check if any element is common among pairs System.out.println( "(" +arr[p.first]+ ", " +arr[p.second]+ ") and (" +arr[i]+ ", " +arr[j]+ ")" ); return true ; } } } return false ; } // Testing program public static void main(String args[]) { int arr[] = { 3 , 4 , 7 , 1 , 2 , 9 , 8 }; ArrayElements a = new ArrayElements(); a.findPairs(arr); } } // This code is contributed by Aakash Hasija |
Python3
# Python Program to find four different elements a,b,c and d of # array such that a+b = c+d # function to find a, b, c, d such that # (a + b) = (c + d) def find_pair_of_sum(arr: list , n: int ): map = {} for i in range (n): for j in range (i + 1 , n): sum = arr[i] + arr[j] if sum in map : print (f "{map[sum]} and ({arr[i]}, {arr[j]})" ) return else : map [ sum ] = (arr[i], arr[j]) # Driver code if __name__ = = "__main__" : arr = [ 3 , 4 , 7 , 1 , 2 , 9 , 8 ] n = len (arr) find_pair_of_sum(arr, n) |
C#
using System; using System.Collections.Generic; // C# Program to find four different elements a,b,c and d of // array such that a+b = c+d public class ArrayElements { // Class to represent a pair public class pair { private readonly ArrayElements outerInstance; public int first, second; public pair(ArrayElements outerInstance, int f, int s) { this .outerInstance = outerInstance; first = f; second = s; } } public virtual bool findPairs( int [] arr) { // Create an empty Hash to store mapping from sum to // pair indexes Dictionary< int , pair> map = new Dictionary< int , pair>(); int n = arr.Length; // Traverse through all possible pairs of arr[] for ( int i = 0; i < n; ++i) { for ( int j = i + 1; j < n; ++j) { // If sum of current pair is not in hash, // then store it and continue to next pair int sum = arr[i] + arr[j]; if (!map.ContainsKey(sum)) { map[sum] = new pair( this , i,j); } else // Else (Sum already present in hash) { // Find previous pair pair p = map[sum]; // Since array elements are distinct, we don't // need to check if any element is common among pairs Console.WriteLine( "(" + arr[p.first] + ", " + arr[p.second] + ") and (" + arr[i] + ", " + arr[j] + ")" ); return true ; } } } return false ; } // Testing program public static void Main( string [] args) { int [] arr = new int [] {3, 4, 7, 1, 2, 9, 8}; ArrayElements a = new ArrayElements(); a.findPairs(arr); } } // This code is contributed by Shrikant13 |
Javascript
<script> // Find four different elements a,b,c and d of array such that // a+b = c+d function findPairs(arr, n) { // Create an empty Hash to store mapping from sum to // pair indexes let Hash = new Map(); // Traverse through all possible pairs of arr[] for (let i = 0; i < n; ++i) { for (let j = i + 1; j < n; ++j) { // If sum of current pair is not in hash, // then store it and continue to next pair let sum = arr[i] + arr[j]; if (!Hash.has(sum)) Hash.set(sum, [i, j]); else // Else (Sum already present in hash) { // Find previous pair let pp = Hash.get(sum); // pp->previous pair // Since array elements are distinct, we don't // need to check if any element is common among pairs document.write( "(" + arr[pp[0]] + ", " + arr[pp[1]] + ") and (" + arr[i] + ", " + arr[j] + ")" ); return true ; } } } document.write( "No pairs found" ); return false ; } // Driver program let arr = [3, 4, 7, 1, 2, 9, 8]; let n = arr.length findPairs(arr, n); </script> |
输出：
(3, 8) and (4, 7)
幸亏 高拉夫·阿希瓦 感谢您提出上述解决方案。 练习： 1） 用数组中允许的重复项扩展上述解决方案。 2） 进一步扩展该解决方案，以打印输出中的所有四倍，而不是仅打印一倍。所有四个字母都应该按字典顺序打印（先小后大）。假设我们有两个解S1和S2。
S1 : a1 b1 c1 d1 ( these are values of indices int the array ) S2 : a2 b2 c2 d2S1 is lexicographically smaller than S2 iff a1 < a2 OR a1 = a2 AND b1 < b2 OR a1 = a2 AND b1 = b2 AND c1 < c2 OR a1 = a2 AND b1 = b2 AND c1 = c2 AND d1 < d2
看见 这 为了解决运动的问题。 相关文章： 找到数组中满足ab=cd的所有对（a，b）和（c，d） 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
