Givet en array arr[] av storlek n och ett heltal X . Ta reda på om det finns en triplett i arrayen som summerar till det givna heltal X .

Exempel:

Inmatning: array = {12, 3, 4, 1, 6, 9}, summa = 24;
Produktion: 12, 3, 9
Förklaring: Det finns en triplett (12, 3 och 9) närvarande
i arrayen vars summa är 24.

Inmatning: matris = {1, 2, 3, 4, 5}, summa = 9
Produktion: 5, 3, 1
Förklaring: Det finns en triplett (5, 3 och 1) närvarande
i arrayen vars summa är 9.

Triplettsumma i array (3sum) genom att generera alla trillingar:

En enkel metod är att generera alla möjliga tripletter och jämföra summan av varje triplett med det givna värdet. Följande kod implementerar denna enkla metod med hjälp av tre kapslade slingor.

Steg-för-steg tillvägagångssätt:

• Med tanke på en mängd längder n och en summa s
• Skapa tre kapslade loopar från början till slut (loopräknare i), andra loopar från i+1 till slut (loopräknare j) och tredje slinga löper från j+1 att avsluta (loopräknare k)
• Räknaren för dessa slingor representerar indexet för 3 beståndsdelar av trillingarna.
• Hitta summan av ith, jth och kth element. Om summan är lika med given summa. Skriv ut tripletten och bryt.
• Om det inte finns någon triplett, skriv ut att det inte finns någon triplett.

Nedan är implementeringen av ovanstående tillvägagångssätt:

C++

verilog alltid

>

>

C

>

>

Java

>

>

Python3

>

>

C#

>

>

Javascript

>

>

PHP

>

>

Triplet is 4, 10, 8>

Komplexitetsanalys:

• Tidskomplexitet: På³), Det finns tre kapslade loopar som korsar arrayen, så tidskomplexiteten är O(n^3)
• Hjälputrymme: O(1), Eftersom inget extra utrymme krävs.

Triplettsumma i array (3sum) använder sig av Två pekare teknik :

Genom att sortera arrayen kan effektiviteten hos algoritmen förbättras. Detta effektiva tillvägagångssätt använder tvåpoängsteknik . Gå igenom arrayen och fixa det första elementet i tripletten. Använd nu Two Pointers-algoritmen för att hitta om det finns ett par vars summa är lika med x – array[i] . Algoritmen för två pekare tar linjär tid så det är bättre än en kapslad loop.

Steg-för-steg tillvägagångssätt:

• Sortera den givna arrayen.
• Slinga över arrayen och fixa det första elementet i den möjliga tripletten, arr[i] .
• Fixa sedan två pekare, en kl i + 1 och den andra kl n – 1 . Och titta på summan,
  • Om summan är mindre än den nödvändiga summan, öka den första pekaren.
  • Annars, om summan är större, minska slutpekaren för att minska summan.
  • Annars, om summan av element vid tvåpekaren är lika med given summa, skriv ut tripletten och bryt.

Nedan är implementeringen av ovanstående tillvägagångssätt:

C++

>

>

C

>

>

Java

hitta i kartan c++

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # Python3 program to find a triplet> # returns true if there is triplet> # with sum equal to 'sum' present> # in A[]. Also, prints the triplet> def> find3Numbers(A, arr_size,>sum>):> ># Sort the elements> >A.sort()> ># Now fix the first element> ># one by one and find the> ># other two elements> >for> i>in> range>(>0>, arr_size>->2>):> > ># To find the other two elements,> ># start two index variables from> ># two corners of the array and> ># move them toward each other> > ># index of the first element> ># in the remaining elements> >l>=> i>+> 1> > ># index of the last element> >r>=> arr_size>->1> >while> (l     if( A[i] + A[l] + A[r] == sum):  print('Triplet is', A[i],   ', ', A[l], ', ', A[r]);  return True    elif (A[i] + A[l] + A[r] summa r -= 1 # Om vi ​​når hit, då # hittades ingen triplett return False # Drivrutinsprogram för att testa ovan funktion A = [1, 4, 45, 6, 10, 8] summa = 22 arr_size = len(A) find3Numbers(A, arr_size, summa) # Detta är bidragit av Smitha Dinesh Semwal>
 
 
 
 
    
 
>
 
    
 
>
 
 
C#
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // C# program to find a triplet> using> System;> class> GFG {> >// returns true if there is triplet> >// with sum equal to 'sum' present> >// in A[]. Also, prints the triplet> >bool> find3Numbers(>int>[] A,>int> arr_size,> >int> sum)> >{> >int> l, r;> >/* Sort the elements */> >quickSort(A, 0, arr_size - 1);> >/* Now fix the first element> >one by one and find the> >other two elements */> >for> (>int> i = 0; i   // To find the other two elements,  // start two index variables from  // two corners of the array and  // move them toward each other  l = i + 1; // index of the first element  // in the remaining elements  r = arr_size - 1; // index of the last element  while (l   if (A[i] + A[l] + A[r] == sum) {  Console.Write('Triplet is ' + A[i] + ', ' + A[l] + ', ' + A[r]);  return true;  }  else if (A[i] + A[l] + A[r]   l++;  else // A[i] + A[l] + A[r]>summa r--;  } } // Om vi ​​når hit, då // ingen triplett hittades return false;  } int partition(int[] A, int si, int ei) { int x = A[ei];  int i = (si - 1);  int j;  för (j = si; j<= ei - 1; j++) {  if (A[j] <= x) {  i++;  int temp = A[i];  A[i] = A[j];  A[j] = temp;  }  }  int temp1 = A[i + 1];  A[i + 1] = A[ei];  A[ei] = temp1;  return (i + 1);  }  /* Implementation of Quick Sort A[] -->Array som ska sorteras si --> Startindex ei --> Slutindex */ void quickSort(int[] A, int si, int ei) { int pi;  /* Partitioneringsindex */ if (si pi = partition(A, si, ei); quickSort(A, si, pi - 1); quickSort(A, pi + 1, ei); } } // Driver Code static tomrum Main() { GFG triplett = new GFG(); int[] A = new int[] { 1, 4, 45, 6, 10, 8 }; (A, arr_size, sum);
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 > // Javascript program to find a triplet> // returns true if there is triplet with sum equal> // to 'sum' present in A[]. Also, prints the triplet> function> find3Numbers(A, arr_size, sum)> {> >let l, r;> >/* Sort the elements */> >A.sort((a,b) =>a-b);> >/* Now fix the first element one> >by one and find the> >other two elements */> >for> (let i = 0; i   // To find the other two  // elements, start two index  // variables from two corners of   // the array and move  // them toward each other    // index of the first element in the  l = i + 1;     // remaining elements    // index of the last element  r = arr_size - 1;   while (l   if (A[i] + A[l] + A[r] == sum)   {  document.write('Triplet is ' + A[i] + ', '  + A[l] + ', ' + A[r]);  return true;  }  else if (A[i] + A[l] + A[r]   l++;  else // A[i] + A[l] + A[r]>summa r--;  } } // Om vi ​​når hit, så hittades ingen triplett return false; } /* Drivrutinsprogram för att testa ovanstående funktion */ låt A = [ 1, 4, 45, 6, 10, 8 ];  låt summa = 22;  låt arr_size = A.längd;  find3Numbers(A, arr_size, summa); // Denna kod är bidragit av Mayank Tyagi>
 
 
 
 
    
 
>
 
    
 
>
 
 
PHP
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
  // PHP program to find a triplet // returns true if there is  // triplet with sum equal to // 'sum' present in A[]. Also, // prints the triplet function find3Numbers($A, $arr_size, $sum) {  $l; $r;  /* Sort the elements */  sort($A);  /* Now fix the first element   one by one and find the  other two elements */  for ($i = 0; $i <$arr_size - 2; $i++)   {  // To find the other two elements,   // start two index variables from   // two corners of the array and   // move them toward each other  $l = $i + 1; // index of the first element   // in the remaining elements  // index of the last element  $r = $arr_size - 1;   while ($l <$r)   {  if ($A[$i] + $A[$l] +   $A[$r] == $sum)  {  echo 'Triplet is ', $A[$i], ' ',  $A[$l], ' ',   $A[$r], '
';  return true;  }  else if ($A[$i] + $A[$l] +  $A[$r] <$sum)  $l++;  else // A[i] + A[l] + A[r]>summa $r--;  } } // Om vi ​​når hit, då // ingen triplett hittades return false; } // Drivrutinskod $A = array (1, 4, 45, 6, 10, 8); $summa = 22; $arr_size = sizeof($A); find3Numbers($A, $arr_size, $summa); // Denna kod är bidragit av ajit ?>>
 
 
 
 
vem är urfi javed
    
 
>
 
    
 
>
 
  Produktion  
 
Triplet is 4, 8, 10>
 
    Komplexitetsanalys:     
 
 
    Tidskomplexitet:    O(N^2), Det finns bara två kapslade loopar som korsar arrayen, så tidskomplexiteten är O(n^2). Två pekare algoritm tar O(n) tid och det första elementet kan fixas med en annan kapslad genomgång.
 
    Hjälputrymme:    O(1), Eftersom inget extra utrymme krävs.
 
 
    Triplettsumma i array (3sum)    använder sig av  Hashing  :
  
 
Detta tillvägagångssätt använder extra utrymme men är enklare än tvåpekare. Kör två slingor yttre slinga från början till slut och inre slinga från    i+1    att sluta. Skapa en hashmap eller ställ in att lagra elementen däremellan    i+1    till    n-1    . Så om den givna summan är    x,    kontrollera om det finns ett nummer i uppsättningen som är lika med    x         – arr[i] – arr[j]    . Om ja, skriv ut tripletten.
 
 
Steg-för-steg tillvägagångssätt:
 
 
Iterera genom arrayen och fixera det första elementet (    A[i]    ) för tripletten.
 
För varje    A[i]    , använd en Hashmap         för att lagra potentiella andra element som fullbordar den önskade summan    (summa – A[i])    .
 
Inuti en kapslad loop, kontrollera om skillnaden mellan det aktuella elementet (    A[j]    ) och önskad summa (    summa – A[i]    ) finns i Hashmap. Om det är det, hittas en triplett, skriv ut den.
 
Om ingen triplett hittas i hela arrayen, returnerar funktionen    falsk    .
 
 
Nedan är implementeringen av ovanstående tillvägagångssätt:
 
C++
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 #include> using> namespace> std;> // Function to find a triplet with a given sum in an array> bool> find3Numbers(>int> A[],>int> arr_size,>int> sum)> {> >// Fix the first element as A[i]> >for> (>int> i = 0; i   // Create a set to store potential second elements  // that complement the desired sum  unordered_set s;  // Beräkna den aktuella summan som behövs för att nå // målsumman int curr_sum = summa - A[i];  // Iterera genom undermatrisen A[i+1..n-1] för att hitta // ett par med den nödvändiga summan för (int j = i + 1; j // Beräkna det nödvändiga värdet för det andra // elementet int required_value = curr_sum - A[j]; // Kontrollera om det obligatoriska värdet finns i //-uppsättningen om (s.find(required_value) != s.end()) { // Skriv ut tripletten /; / elements printf('Trippel är %d, %d, %d', A[i], A[j], returnerar true } // Lägg till det aktuella elementet för framtida // komplement kontrollerar s.insert(A[j]); 4, 45, 6, 10, 8 }; int summa = 22; int arr_size = sizeof(A) / sizeof(A[0]); find3Numbers(A, arr_size, summa return 0 }>
 
 
 
 
    
 
>
 
    
 
>
 
 
Java
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 import> java.util.HashSet;> public> class> TripletSumFinder {> >// Function to find a triplet with a given sum in an> >// array> >public> static> boolean> >find3Numbers(>int>[] A,>int> arr_size,>int> sum)> >{> >// Fix the first element as A[i]> >for> (>int> i =>0>; i 2; i++) {  // Create a HashSet to store potential second  // elements that complement the desired sum  HashSet s = new HashSet();  // Calculate the current sum needed to reach the  // target sum  int curr_sum = sum - A[i];  // Iterate through the subarray A[i+1..n-1] to  // find a pair with the required sum  for (int j = i + 1; j   // Calculate the required value for the  // second element  int required_value = curr_sum - A[j];  // Check if the required value is present in  // the HashSet  if (s.contains(required_value)) {  // Triplet is found; print the triplet  // elements  System.out.println('Triplet is ' + A[i]  + ', ' + A[j] + ', '  + required_value);  return true;  }  // Add the current element to the HashSet  // for future complement checks  s.add(A[j]);  }  }  // If no triplet is found, return false  return false;  }  public static void main(String[] args)  {  int[] A = { 1, 4, 45, 6, 10, 8 };  int sum = 22;  int arr_size = A.length;  // Call the find3Numbers function to find and print  // the triplet, if it exists  if (!find3Numbers(A, arr_size, sum)) {  System.out.println(  'No triplet found with the given sum.');  }  } }>
 
 
 
 
    
 
>
 
    
 
>
 
 
Python3
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # Function to find a triplet with a given sum in an array> def> find3Numbers(arr,>sum>):> ># Fix the first element as arr[i]> >for> i>in> range>(>len>(arr)>-> 2>):> ># Create a set to store potential second elements that complement the desired sum> >s>=> set>()> ># Calculate the current sum needed to reach the target sum> >curr_sum>=> sum> -> arr[i]> ># Iterate through the subarray arr[i+1:]> >for> j>in> range>(i>+> 1>,>len>(arr)):> ># Calculate the required value for the second element> >required_value>=> curr_sum>-> arr[j]> ># Check if the required value is present in the set> >if> required_value>in> s:> ># Triplet is found; print the triplet elements> >print>(f>'Triplet is {arr[i]}, {arr[j]}, {required_value}'>)> >return> True> ># Add the current element to the set for future complement checks> >s.add(arr[j])> ># If no triplet is found, return False> >return> False> # Driver program to test above function> if> __name__>=>=> '__main__'>:> >arr>=> [>1>,>4>,>45>,>6>,>10>,>8>]> >target_sum>=> 22> ># Call the find3Numbers function to find and print the triplet, if it exists> >if> not> find3Numbers(arr, target_sum):> >print>(>'No triplet found.'>)> 
 
 
 
 
    
 
>
 
    
 
>
 
 
C#
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 using> System;> using> System.Collections.Generic;> class> Program {> >// Function to find a triplet with a given sum in an> >// array> >static> bool> Find3Numbers(>int>[] arr,>int> sum)> >{> >// Fix the first element as arr[i]> >for> (>int> i = 0; i   // Create a HashSet to store potential second  // elements that complement the desired sum  HashSet s = nytt HashSet ();  // Beräkna den aktuella summan som behövs för att nå // målsumman int curr_sum = summa - arr[i];  // Iterera genom undermatrisen arr[i+1:] för (int j = i + 1; j // Beräkna det nödvändiga värdet för // andra elementet int required_value = curr_sum - arr[j]; // Kontrollera om det obligatoriska värdet finns i // HashSet if (s.Contains(required_value)) { // Triplet hittas skriv ut tripletten // element Console.WriteLine('Triplet är ' + arr[i] + ', ' + arr[j] + ', ' + required_value return true } // Lägg till det aktuella elementet i HashSet // för framtida komplementkontroller s.Add(arr[j]); Om ingen triplett hittas, returnera false return false } // Drivrutinsprogram för att testa Find3Numbers-funktionen static void Main() { int[] arr = { 1, 4, 45, 6, 10, 8 }; ; // Anrop Find3Numbers-funktionen för att hitta och skriva ut // tripletten, om den finns om (!Find3Numbers(arr, target_sum)) { Console.WriteLine('Ingen triplett hittades.');
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 function> find3Numbers(A, sum) {> >// Fix the first element as A[i]> >for> (let i = 0; i   // Create a Set to store potential second elements that complement the desired sum  const s = new Set();  // Calculate the current sum needed to reach the target sum  const currSum = sum - A[i];  // Iterate through the subarray A[i+1..n-1] to find a pair with the required sum  for (let j = i + 1; j   // Calculate the required value for the second element  const requiredValue = currSum - A[j];  // Check if the required value is present in the Set  if (s.has(requiredValue)) {  // Triplet is found; print the triplet elements  console.log(`Triplet is ${A[i]}, ${A[j]}, ${requiredValue}`);  return true;  }  // Add the current element to the Set for future complement checks  s.add(A[j]);  }  }  // If no triplet is found, return false  return false; } function main() {  const A = [1, 4, 45, 6, 10, 8];  const sum = 22;  // Call the find3Numbers function to find and print the triplet, if it exists  if (!find3Numbers(A, sum)) {  console.log('No triplet found with the given sum.');  } } // Call the main function to start the program main();>
 
 
 
 
    
 
>
 
    
 
>
 
  Produktion  
 
Triplet is 4, 8, 10>
 
    Tidskomplexitet:    O(N^2)  
    Hjälputrymme:    O(N), eftersom n extra utrymme har tagits
 
Du kan se förklaringen av problemet på  Youtube  diskuteras av Geeks For Geeks Team.
 
Du kan också hänvisa  detta  video presenterad på Youtube.  
    Hur skriver man ut alla trillingar med given summa?       
Hänvisa Hitta alla trillingar med nollsumma .