给定三个整数数组和一个“和”,任务是检查是否有三个元素a、b、c,以便a+b+c=和,a、b和c属于三个不同的数组。
null
例如:
Input : a1[] = { 1 , 2 , 3 , 4 , 5 }; a2[] = { 2 , 3 , 6 , 1 , 2 }; a3[] = { 3 , 2 , 4 , 5 , 6 }; sum = 9Output : Yes1 + 2 + 6 = 9 here 1 from a1[] and 2 froma2[] and 6 from a3[] Input : a1[] = { 1 , 2 , 3 , 4 , 5 }; a2[] = { 2 , 3 , 6 , 1 , 2 }; a3[] = { 3 , 2 , 4 , 5 , 6 }; sum = 20 Output : No
A. 幼稚的方法 就是运行三个循环,检查不同数组中三个元素的和是否等于给定的数字,如果找到,则打印存在,否则打印不存在。
C++
// C++ program to find three element // from different three arrays such // that a + b + c is equal to // given sum #include<bits/stdc++.h> using namespace std; // Function to check if there is // an element from each array such // that sum of the three elements // is equal to given sum. bool findTriplet( int a1[], int a2[], int a3[], int n1, int n2, int n3, int sum) { for ( int i = 0; i < n1; i++) for ( int j = 0; j < n2; j++) for ( int k = 0; k < n3; k++) if (a1[i] + a2[j] + a3[k] == sum) return true ; return false ; } // Driver Code int main() { int a1[] = { 1 , 2 , 3 , 4 , 5 }; int a2[] = { 2 , 3 , 6 , 1 , 2 }; int a3[] = { 3 , 2 , 4 , 5 , 6 }; int sum = 9; int n1 = sizeof (a1) / sizeof (a1[0]); int n2 = sizeof (a2) / sizeof (a2[0]); int n3 = sizeof (a3) / sizeof (a3[0]); findTriplet(a1, a2, a3, n1, n2, n3, sum)? cout << "Yes" : cout << "No" ; return 0; } |
JAVA
// Java program to find three element // from different three arrays such // that a + b + c is equal to // given sum class GFG { // Function to check if there is // an element from each array such // that sum of the three elements // is equal to given sum. static boolean findTriplet( int a1[], int a2[], int a3[], int n1, int n2, int n3, int sum) { for ( int i = 0 ; i < n1; i++) for ( int j = 0 ; j < n2; j++) for ( int k = 0 ; k < n3; k++) if (a1[i] + a2[j] + a3[k] == sum) return true ; return false ; } // Driver code public static void main (String[] args) { int a1[] = { 1 , 2 , 3 , 4 , 5 }; int a2[] = { 2 , 3 , 6 , 1 , 2 }; int a3[] = { 3 , 2 , 4 , 5 , 6 }; int sum = 9 ; int n1 = a1.length; int n2 = a2.length; int n3 = a3.length; if (findTriplet(a1, a2, a3, n1, n2, n3, sum)) System.out.print( "Yes" ); else System.out.print( "No" ); } } // This code is contributed by Anant Agarwal. |
Python3
# Python3 program to find # three element from different # three arrays such that # a + b + c is equal to # given sum # Function to check if there # is an element from each # array such that sum of the # three elements is equal to # given sum. def findTriplet(a1, a2, a3, n1, n2, n3, sum ): for i in range ( 0 , n1): for j in range ( 0 , n2): for k in range ( 0 , n3): if (a1[i] + a2[j] + a3[k] = = sum ): return True return False # Driver Code a1 = [ 1 , 2 , 3 , 4 , 5 ] a2 = [ 2 , 3 , 6 , 1 , 2 ] a3 = [ 3 , 2 , 4 , 5 , 6 ] sum = 9 n1 = len (a1) n2 = len (a2) n3 = len (a3) print ( "Yes" ) if findTriplet(a1, a2, a3, n1, n2, n3, sum ) else print ( "No" ) # This code is contributed # by Smitha |
C#
// C# program to find three element // from different three arrays such // that a + b + c is equal to // given sum using System; public class GFG { // Function to check if there is an // element from each array such that // sum of the three elements is // equal to given sum. static bool findTriplet( int []a1, int []a2, int []a3, int n1, int n2, int n3, int sum) { for ( int i = 0; i < n1; i++) for ( int j = 0; j < n2; j++) for ( int k = 0; k < n3; k++) if (a1[i] + a2[j] + a3[k] == sum) return true ; return false ; } // Driver Code static public void Main () { int []a1 = {1 , 2 , 3 , 4 , 5}; int []a2 = {2 , 3 , 6 , 1 , 2}; int []a3 = {3 , 2 , 4 , 5 , 6}; int sum = 9; int n1 = a1.Length; int n2 = a2.Length; int n3 = a3.Length; if (findTriplet(a1, a2, a3, n1, n2, n3, sum)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to find three element // from different three arrays such // that a + b + c is equal to // given sum // Function to check if there is an // element from each array such that // sum of the three elements is equal // to given sum. function findTriplet( $a1 , $a2 , $a3 , $n1 , $n2 , $n3 , $sum ) { for ( $i = 0; $i < $n1 ; $i ++) for ( $j = 0; $j < $n2 ; $j ++) for ( $k = 0; $k < $n3 ; $k ++) if ( $a1 [ $i ] + $a2 [ $j ] + $a3 [ $k ] == $sum ) return true; return false; } // Driver Code $a1 = array ( 1 , 2 , 3 , 4 , 5 ); $a2 = array ( 2 , 3 , 6 , 1 , 2 ); $a3 = array ( 3 , 2 , 4 , 5 , 6 ); $sum = 9; $n1 = count ( $a1 ); $n2 = count ( $a2 ); $n3 = count ( $a3 ); if (findTriplet( $a1 , $a2 , $a3 , $n1 , $n2 , $n3 , $sum )==true) echo "Yes" ; else echo "No" ; // This code is contributed by anuj_67. ?> |
Javascript
<script> // JavaScript program to find three element // from different three arrays such // that a + b + c is equal to // given sum // Function to check if there is // an element from each array such // that sum of the three elements // is equal to given sum. function findTriplet(a1, a2, a3, n1, n2, n3, sum) { for ( var i = 0; i < n1; i++) for ( var j = 0; j < n2; j++) for ( var k = 0; k < n3; k++) if (a1[i] + a2[j] + a3[k] == sum) return true ; return false ; } // Driver Code var a1 = [ 1 , 2 , 3 , 4 , 5 ]; var a2 = [ 2 , 3 , 6 , 1 , 2 ]; var a3 = [ 3 , 2 , 4 , 5 , 6 ]; var sum = 9; var n1 = a1.length; var n2 = a2.length; var n3 = a3.length; findTriplet(a1, a2, a3, n1, n2, n3, sum)? document.write( "Yes" ) : document.write( "No" ); </script> |
输出:
Yes
时间复杂性: O(n) 3. ) 空间复杂性: O(1)
一 有效解决方案 就是将第一个数组的所有元素存储在哈希表(C++中的无序_集)中,然后逐个计算最后两个数组元素的两个元素之和,并从给定的数字k中减去,如果哈希表中存在,则签入哈希表,然后打印存在,否则不存在。
1. Store all elements of first array in hash table2. Generate all pairs of elements from two arrays using nested loop. For every pair (a1[i], a2[j]), check if sum - (a1[i] + a2[j]) exists in hash table. If yes return true.
下面是上述想法的实现。
C++
// C++ program to find three element // from different three arrays such // that a + b + c is equal to // given sum #include<bits/stdc++.h> using namespace std; // Function to check if there is // an element from each array such // that sum of the three elements is // equal to given sum. bool findTriplet( int a1[], int a2[], int a3[], int n1, int n2, int n3, int sum) { // Store elements of // first array in hash unordered_set < int > s; for ( int i = 0; i < n1; i++) s.insert(a1[i]); // sum last two arrays // element one by one for ( int i = 0; i < n2; i++) { for ( int j = 0; j < n3; j++) { // Consider current pair and // find if there is an element // in a1[] such that these three // form a required triplet if (s.find(sum - a2[i] - a3[j]) != s.end()) return true ; } } return false ; } // Driver Code int main() { int a1[] = { 1 , 2 , 3 , 4 , 5 }; int a2[] = { 2 , 3 , 6 , 1 , 2 }; int a3[] = { 3 , 2 , 4 , 5 , 6 }; int sum = 9; int n1 = sizeof (a1) / sizeof (a1[0]); int n2 = sizeof (a2) / sizeof (a2[0]); int n3 = sizeof (a3) / sizeof (a3[0]); findTriplet(a1, a2, a3, n1, n2, n3, sum)? cout << "Yes" : cout << "No" ; return 0; } |
JAVA
// Java program to find three element // from different three arrays such // that a + b + c is equal to // given sum import java.util.*; class GFG { // Function to check if there is // an element from each array such // that sum of the three elements is // equal to given sum. static boolean findTriplet( int a1[], int a2[], int a3[], int n1, int n2, int n3, int sum) { // Store elements of // first array in hash HashSet<Integer> s = new HashSet<Integer>(); for ( int i = 0 ; i < n1; i++) { s.add(a1[i]); } // sum last two arrays // element one by one ArrayList<Integer> al = new ArrayList<>(s); for ( int i = 0 ; i < n2; i++) { for ( int j = 0 ; j < n3; j++) { // Consider current pair and // find if there is an element // in a1[] such that these three // form a required triplet if (al.contains(sum - a2[i] - a3[j]) & al.indexOf(sum - a2[i] - a3[j]) != al.get(al.size() - 1 )) { return true ; } } } return false ; } // Driver Code public static void main(String[] args) { int a1[] = { 1 , 2 , 3 , 4 , 5 }; int a2[] = { 2 , 3 , 6 , 1 , 2 }; int a3[] = { 3 , 2 , 4 , 5 , 6 }; int sum = 9 ; int n1 = a1.length; int n2 = a2.length; int n3 = a3.length; if (findTriplet(a1, a2, a3, n1, n2, n3, sum)) { System.out.println( "Yes" ); } else { System.out.println( "No" ); } } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to find three element # from different three arrays such # that a + b + c is equal to # given sum # Function to check if there is # an element from each array such # that sum of the three elements is # equal to given sum. def findTriplet(a1, a2, a3, n1, n2, n3, sum ): # Store elements of first # array in hash s = set () # sum last two arrays element # one by one for i in range (n1): s.add(a1[i]) for i in range (n2): for j in range (n3): # Consider current pair and # find if there is an element # in a1[] such that these three # form a required triplet if sum - a2[i] - a3[j] in s: return True return False # Driver code a1 = [ 1 , 2 , 3 , 4 , 5 ] a2 = [ 2 , 3 , 6 , 1 , 2 ] a3 = [ 3 , 24 , 5 , 6 ] n1 = len (a1) n2 = len (a2) n3 = len (a3) sum = 9 if findTriplet(a1, a2, a3, n1, n2, n3, sum ) = = True : print ( "Yes" ) else : print ( "No" ) # This code is contributed by Shrikant13 |
C#
// C# program to find three element // from different three arrays such // that a + b + c is equal to // given sum using System; using System.Collections.Generic; class GFG { // Function to check if there is // an element from each array such // that sum of the three elements is // equal to given sum. static bool findTriplet( int []a1, int []a2, int []a3, int n1, int n2, int n3, int sum) { // Store elements of // first array in hash HashSet< int > s = new HashSet< int >(); for ( int i = 0; i < n1; i++) { s.Add(a1[i]); } // sum last two arrays // element one by one List< int > al = new List< int >(s); for ( int i = 0; i < n2; i++) { for ( int j = 0; j < n3; j++) { // Consider current pair and // find if there is an element // in a1[] such that these three // form a required triplet if (al.Contains(sum - a2[i] - a3[j]) & al.IndexOf(sum - a2[i] - a3[j]) != al[al.Count - 1]) { return true ; } } } return false ; } // Driver Code public static void Main(String[] args) { int []a1 = {1, 2, 3, 4, 5}; int []a2 = {2, 3, 6, 1, 2}; int []a3 = {3, 2, 4, 5, 6}; int sum = 9; int n1 = a1.Length; int n2 = a2.Length; int n3 = a3.Length; if (findTriplet(a1, a2, a3, n1, n2, n3, sum)) { Console.WriteLine( "Yes" ); } else { Console.WriteLine( "No" ); } } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript program to find three element // from different three arrays such // that a + b + c is equal to // given sum // Function to check if there is // an element from each array such // that sum of the three elements is // equal to given sum. function findTriplet(a1, a2, a3, n1, n2, n3, sum) { // Store elements of // first array in hash var s = new Set(); for ( var i = 0; i < n1; i++) s.add(a1[i]); // sum last two arrays // element one by one for ( var i = 0; i < n2; i++) { for ( var j = 0; j < n3; j++) { // Consider current pair and // find if there is an element // in a1[] such that these three // form a required triplet if (s.has(sum - a2[i] - a3[j])) return true ; } } return false ; } // Driver Code var a1 = [1 , 2 , 3 , 4 , 5]; var a2 = [2 , 3 , 6 , 1 , 2]; var a3 = [3 , 2 , 4 , 5 , 6]; var sum = 9; var n1 = a1.length; var n2 = a2.length; var n3 = a3.length; findTriplet(a1, a2, a3, n1, n2, n3, sum)? document.write( "Yes" ): document.write( "No" ); // This code is contributed by famously. </script> |
输出:
Yes
时间复杂性: O(n) 2. ) 辅助空间: O(n)
本文由 丹麦拉扎 .如果你喜欢GeekSforgek,并想贡献自己的力量,你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上,并帮助其他极客。 如果您发现任何不正确的地方,或者您想分享有关上述主题的更多信息,请写下评论。
© 版权声明
文章版权归作者所有,未经允许请勿转载。
THE END