我们有一个整数数组，我们必须在数组中找到两个这样的元素，这两个元素的和等于数组中其余元素的和。
null
例如：
Input : arr[] = {2, 11, 5, 1, 4, 7}Output : Elements are 4 and 11Note that 4 + 11 = 2 + 5 + 1 + 7Input : arr[] = {2, 4, 2, 1, 11, 15}Output : Elements do not exist
A. 简单解决方案 是一个一个地考虑每一对，找到它的总和，并将之和其余元素之和进行比较。如果我们找到一个和其余元素的和相等的对，我们打印该对并返回true。该解的时间复杂度为O（n） 3. )
一 有效解决方案 就是求所有数组元素的和。让这个总和成为“总和”。现在，任务简化为找到一个sum等于sum/2的对。 另一个优化是，只有当整个数组的和为偶数时，一对才可能存在，因为我们基本上是将它分成两个和相等的部分。 1- 求整个数组的和。让这个总和成为“总和” 2- 如果sum为奇数，则返回false。 3- 使用所讨论的基于散列的方法，找到一个sum等于“sum/2”的对 在这里 如方法2所示。如果找到一对，请打印它并返回true。 4- 如果不存在对，则返回false。
以下是上述步骤的实施情况。
C++
// C++ program to find whether two elements exist // whose sum is equal to sum of rest of the elements. #include<bits/stdc++.h> using namespace std; // Function to check whether two elements exist // whose sum is equal to sum of rest of the elements. bool checkPair( int arr[], int n) { // Find sum of whole array int sum = 0; for ( int i=0; i<n; i++) sum += arr[i]; // If sum of array is not even than we can not // divide it into two part if (sum%2 != 0) return false ; sum = sum/2; // For each element arr[i], see if there is // another element with value sum - arr[i] unordered_set< int > s; for ( int i=0; i<n; i++) { int val = sum-arr[i]; // If element exist than return the pair if (s.find(val) != s.end()) { printf ( "Pair elements are %d and %d" , arr[i], val); return true ; } s.insert(arr[i]); } return false ; } // Driver program. int main() { int arr[] = {2, 11, 5, 1, 4, 7}; int n = sizeof (arr)/ sizeof (arr[0]); if (checkPair(arr, n) == false ) printf ( "No pair found" ); return 0; } |
JAVA
// Java program to find whether two elements exist // whose sum is equal to sum of rest of the elements. import java.util.*; class GFG { // Function to check whether two elements exist // whose sum is equal to sum of rest of the elements. static boolean checkPair( int arr[], int n) { // Find sum of whole array int sum = 0 ; for ( int i = 0 ; i < n; i++) { sum += arr[i]; } // If sum of array is not even than we can not // divide it into two part if (sum % 2 != 0 ) { return false ; } sum = sum / 2 ; // For each element arr[i], see if there is // another element with value sum - arr[i] HashSet<Integer> s = new HashSet<Integer>(); for ( int i = 0 ; i < n; i++) { int val = sum - arr[i]; // If element exist than return the pair if (s.contains(val) && val == ( int ) s.toArray()[s.size() - 1 ]) { System.out.printf( "Pair elements are %d and %d" , arr[i], val); return true ; } s.add(arr[i]); } return false ; } // Driver program. public static void main(String[] args) { int arr[] = { 2 , 11 , 5 , 1 , 4 , 7 }; int n = arr.length; if (checkPair(arr, n) == false ) { System.out.printf( "No pair found" ); } } } /* This code contributed by PrinciRaj1992 */ |
Python3
# Python3 program to find whether # two elements exist whose sum is # equal to sum of rest of the elements. # Function to check whether two # elements exist whose sum is equal # to sum of rest of the elements. def checkPair(arr, n): s = set () sum = 0 # Find sum of whole array for i in range (n): sum + = arr[i] # / If sum of array is not # even than we can not # divide it into two part if sum % 2 ! = 0 : return False sum = sum / 2 # For each element arr[i], see if # there is another element with # value sum - arr[i] for i in range (n): val = sum - arr[i] if arr[i] not in s: s.add(arr[i]) # If element exist than # return the pair if val in s: print ( "Pair elements are" , arr[i], "and" , int (val)) # Driver Code arr = [ 2 , 11 , 5 , 1 , 4 , 7 ] n = len (arr) if checkPair(arr, n) = = False : print ( "No pair found" ) # This code is contributed # by Shrikant13 |
C#
// C# program to find whether two elements exist // whose sum is equal to sum of rest of the elements. using System; using System.Collections.Generic; class GFG { // Function to check whether two elements exist // whose sum is equal to sum of rest of the elements. static bool checkPair( int []arr, int n) { // Find sum of whole array int sum = 0; for ( int i = 0; i < n; i++) { sum += arr[i]; } // If sum of array is not even than we can not // divide it into two part if (sum % 2 != 0) { return false ; } sum = sum / 2; // For each element arr[i], see if there is // another element with value sum - arr[i] HashSet< int > s = new HashSet< int >(); for ( int i = 0; i < n; i++) { int val = sum - arr[i]; // If element exist than return the pair if (s.Contains(val)) { Console.Write( "Pair elements are {0} and {1}" , arr[i], val); return true ; } s.Add(arr[i]); } return false ; } // Driver code public static void Main(String[] args) { int []arr = {2, 11, 5, 1, 4, 7}; int n = arr.Length; if (checkPair(arr, n) == false ) { Console.Write( "No pair found" ); } } } // This code contributed by Rajput-Ji |
PHP
<?php // PHP program to find whether two elements exist // whose sum is equal to sum of rest of the elements. // Function to check whether two elements exist // whose sum is equal to sum of rest of the elements. function checkPair(& $arr , $n ) { // Find sum of whole array $sum = 0; for ( $i = 0; $i < $n ; $i ++) $sum += $arr [ $i ]; // If sum of array is not even than we // can not divide it into two part if ( $sum % 2 != 0) return false; $sum = $sum / 2; // For each element arr[i], see if there is // another element with value sum - arr[i] $s = array (); for ( $i = 0; $i < $n ; $i ++) { $val = $sum - $arr [ $i ]; // If element exist than return the pair if ( array_search ( $val , $s )) { echo "Pair elements are " . $arr [ $i ] . " and " . $val . "" ; return true; } array_push ( $s , $arr [ $i ]); } return false; } // Driver Code $arr = array (2, 11, 5, 1, 4, 7); $n = sizeof( $arr ); if (checkPair( $arr , $n ) == false) echo "No pair found" ; // This code is contributed by ita_c ?> |
Javascript
<script> // Javascript program to find // whether two elements exist // whose sum is equal to sum of rest // of the elements. // Function to check whether // two elements exist // whose sum is equal to sum of // rest of the elements. function checkPair(arr,n) { // Find sum of whole array let sum = 0; for (let i = 0; i < n; i++) { sum += arr[i]; } // If sum of array is not even than we can not // divide it into two part if (sum % 2 != 0) { return false ; } sum = Math.floor(sum / 2); // For each element arr[i], see if there is // another element with value sum - arr[i] let s = new Set(); for (let i = 0; i < n; i++) { let val = sum - arr[i]; // If element exist than return the pair if (!s.has(arr[i])) { s.add(arr[i]) } if (s.has(val) ) { document.write( "Pair elements are " + arr[i]+ " and " + val+ "<br>" ); return true ; } s.add(arr[i]); } return false ; } // Driver program. let arr=[2, 11, 5, 1, 4, 7]; let n = arr.length; if (checkPair(arr, n) == false ) { document.write( "No pair found" ); } // This code is contributed by rag2127 </script> |
输出：
Pair elements are 4 and 11
时间复杂性： O（n）。 无序集 使用哈希实现。这里假设哈希搜索和插入的时间复杂度为O（1）。
本文由 尼蒂什·库马尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.cppku.com/wp-content/themes/zibll/img/thumbnail.svg)
