Givet et array arr[] af størrelse n og et heltal x . Find om der er en triplet i arrayet, som summerer op til det givne heltal x .

Eksempler:

Input: matrix = {12, 3, 4, 1, 6, 9}, sum = 24;
Produktion: 12, 3, 9
Forklaring: Der er en triplet (12, 3 og 9) til stede
i arrayet, hvis sum er 24.

Input: matrix = {1, 2, 3, 4, 5}, sum = 9
Produktion: 5, 3, 1
Forklaring: Der er en triplet (5, 3 og 1) til stede
i arrayet, hvis sum er 9.

Tripletsum i array (3sum) ved at generere alle trillingerne:

En simpel metode er at generere alle mulige tripletter og sammenligne summen af ​​hver triplet med den givne værdi. Følgende kode implementerer denne enkle metode ved hjælp af tre indlejrede sløjfer.

Trin-for-trin tilgang:

• Givet en række længder n og en sum s
• Opret tre indlejrede løkke første løkkeløb fra start til slut (løkketæller i), anden løkke løber fra i+1 til ende (løkketæller j) og tredje sløjfe løber fra j+1 at afslutte (løkketæller k)
• Tælleren for disse sløjfer repræsenterer indekset for 3 elementer af trillingerne.
• Find summen af ​​ith, jth og kth element. Hvis summen er lig med given sum. Print tripletten og bryd.
• Hvis der ikke er nogen triplet, så udskriv, at der ikke findes nogen triplet.

Nedenfor er implementeringen af ​​ovenstående tilgang:

C++

>

>

C

>

>

Java

>

>

Python3

hvor mange nuller i 1 mia

>

>

C#

>

>

Javascript

>

>

PHP

>

>

Triplet is 4, 10, 8>

Kompleksitetsanalyse:

• Tidskompleksitet: På³), Der er tre indlejrede sløjfer, der krydser arrayet, så tidskompleksiteten er O(n^3)
• Hjælpeplads: O(1), Da der ikke kræves ekstra plads.

Tripletsum i array (3sum) ved brug af To pointer teknik :

Ved at sortere arrayet kan effektiviteten af ​​algoritmen forbedres. Denne effektive tilgang bruger to-pointer teknik . Gå gennem arrayet og fiks det første element af tripletten. Brug nu Two Pointers-algoritmen til at finde ud af, om der er et par, hvis sum er lig med x – matrix[i] . To pointers algoritme tager lineær tid, så den er bedre end en indlejret løkke.

Trin-for-trin tilgang:

• Sorter det givne array.
• Sløjfe over arrayet og fikser det første element af den mulige triplet, arr[i] .
• Reparer derefter to pointere, en kl i + 1 og den anden kl n – 1 . Og se på summen,
  • Hvis summen er mindre end den nødvendige sum, øges den første pointer.
  • Ellers, hvis summen er større, formindsk slutmarkøren for at reducere summen.
  • Ellers, hvis summen af ​​elementer ved to-pointer er lig med given sum, så udskriv tripletten og bryd.

Nedenfor er implementeringen af ​​ovenstående tilgang:

C++

>

>

C

>

>

Java

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # 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] sum r -= 1 # Hvis vi når hertil, så # blev der ikke fundet nogen triplet retur Falsk # Driverprogram til at teste ovenstående funktion A = [1, 4, 45, 6, 10, 8] sum = 22 arr_size = len(A) find3Numbers(A, arr_size, sum) # Dette er bidraget af 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]>sum r--;  } } // Hvis vi når hertil, så // blev ingen triplet fundet return false;  } int partition(int[] A, int si, int ei) { int x = A[ei];  int i = (si - 1);  int j;  for (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 skal sorteres si --> Startindeks ei --> Slutindeks */ void quickSort(int[] A, int si, int ei) { int pi;  /* Partitioneringsindeks */ if (si pi = partition(A, si, ei); quickSort(A, si, pi - 1); quickSort(A, pi + 1, ei); } } // Driverkode statisk ugyldig Main() { GFG triplet = new GFG(); int [] A = new int[] { 1, 4, 45, 6, 10, 8 }; (A, arr_size, sum); } } // Denne kode er bidraget med mits>
 
 
 
 
    
 
>
 
    
 
>
 
 
Javascript
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 > // 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]>sum r--;  } } // Hvis vi når hertil, så blev ingen triplet fundet return false; } /* Driverprogram til at teste ovenstående funktion */ lad A = [ 1, 4, 45, 6, 10, 8 ];  lad sum = 22;  lad arr_size = A.længde;  find3Numbers(A, arr_size, sum); // Denne kode er bidraget af 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]>sum $r--;  } } // Hvis vi når hertil, så // blev ingen triplet fundet return false; } // Driverkode $A = array (1, 4, 45, 6, 10, 8); $sum = 22; $arr_size = sizeof($A); find3Numbers($A, $arr_size, $sum); // Denne kode er bidraget af ajit ?>>
 
 
 
 
    
 
>
 
    
 
>
 
  Produktion  
 
Triplet is 4, 8, 10>
 
    Kompleksitetsanalyse:     
 
 
    Tidskompleksitet:    O(N^2), Der er kun to indlejrede sløjfer, der krydser arrayet, så tidskompleksiteten er O(n^2). To pointers algoritme tager O(n) tid, og det første element kan rettes ved hjælp af en anden indlejret traversal.
 
    Hjælpeplads:    O(1), Da der ikke kræves ekstra plads.
 
 
    Tripletsum i array (3sum)    ved brug af  Hashing  :
  
 
Denne tilgang bruger ekstra plads, men er enklere end to-pointer-tilgangen. Kør to løkker ydre løkke fra start til slut og indre løkke fra    i+1    at afslutte. Opret et hashmap eller sæt til at gemme elementerne imellem    i+1    til    n-1    . Så hvis den givne sum er    x,    tjek om der er et tal i sættet som er lig med    x         – arr[i] – arr[j]    . Hvis ja, udskriv tripletten.
 
 
Trin-for-trin tilgang:
 
 
Iterér gennem arrayet og fikser det første element (    A[i]    ) for tripletten.
 
For hver    A[i]    , brug en Hashmap         at gemme potentielle sekundære elementer, der fuldender den ønskede sum    (sum – A[i])    .
 
Inde i en indlejret løkke skal du kontrollere, om forskellen mellem det aktuelle element (    A[j]    ) og den ønskede sum (    sum – A[i]    ) findes i Hashmap. Hvis det er, findes en triplet, så udskriv den.
 
Hvis der ikke findes nogen triplet i hele arrayet, vender funktionen tilbage    falsk    .
 
 
Nedenfor er implementeringen af ​​ovenstående tilgang:
 
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;  // Beregn den aktuelle sum, der er nødvendig for at nå // målsummen int curr_sum = sum - A[i];  // Iterer gennem underarrayet A[i+1..n-1] for at finde // et par med den nødvendige sum for (int j = i + 1; j // Beregn den nødvendige værdi for det andet // element int required_value = curr_sum - A[j]; // Kontroller, om den påkrævede værdi er til stede i //-sættet, hvis (s.find(required_value) != s.end()) { // udskriv tripletten /; / elements printf('Triplet er %d, %d, %d', A[i], A[j], returnerer true } // Tilføj det aktuelle element til sættet for fremtidig // komplement checks s.insert(A[j]); } } // Hvis ingen triplet findes, returner false return false } /* Driverprogram for at teste ovenstående funktion */ int main() { int A[] = { 1, 4, 45, 6, 10, 8 }; int sum = 22; int arr_size = sizeof(A) / sizeof(A[0]); find3Numbers(A, arr_size, sum 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 = nyt HashSet ();  // Beregn den aktuelle sum, der er nødvendig for at nå // målsummen int curr_sum = sum - arr[i];  // Iterer gennem underarrayet arr[i+1:] for (int j = i + 1; j // Beregn den nødvendige værdi for // andet element int required_value = curr_sum - arr[j]; // Tjek om påkrævet værdi er til stede i // HashSet if (s.Contains(required_value)) { // Triplet er fundet udskriv triplet // elementer Console.WriteLine('Triplet er ' + arr[i] + ', ' + arr[j] + ', ' + required_value return true } // Tilføj det aktuelle element til HashSet // for fremtidige komplementkontrol s.Add(arr[j]); Hvis der ikke findes nogen triplet, returner falsk return false } // Driverprogram for at teste Find3Numbers-funktionen static void Main() { int[] arr = { 1, 4, 45, 6, 10, 8 }; ; // Kald Find3Numbers-funktionen for at finde og udskrive // ​​tripletten, hvis den findes, hvis (!Find3Numbers(arr, target_sum)) { Console.WriteLine('Ingen triplet fundet.');
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 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  
strengformater
 
Triplet is 4, 8, 10>
 
    Tidskompleksitet:    O(N^2)  
    Hjælpeplads:    O(N), da der er taget n ekstra plads
 
Du kan se forklaringen af ​​problemet på  Youtube  diskuteret af Geeks For Geeks Team.
 
Du kan også henvise  det her  video til stede på Youtube.  
    Hvordan udskriver man alle trillinger med en given sum?       
Henvise Find alle trillinger med nulsum .