Annettu joukko arr[] kooltaan n ja kokonaisluku X . Selvitä, onko taulukossa tripletti, joka summautuu annettuun kokonaislukuun X .

Esimerkkejä:

Syöte: taulukko = {12, 3, 4, 1, 6, 9}, summa = 24;
Lähtö: 12, 3, 9
Selitys: Mukana on kolmos (12, 3 ja 9).
taulukossa, jonka summa on 24.

Syöte: taulukko = {1, 2, 3, 4, 5}, summa = 9
Lähtö: 5, 3, 1
Selitys: Mukana on kolmos (5, 3 ja 1).
taulukossa, jonka summa on 9.

Triplet Sum in Array (3sum) luomalla kaikki kolmiot:

Yksinkertainen tapa on luoda kaikki mahdolliset tripletit ja verrata jokaisen tripletin summaa annettuun arvoon. Seuraava koodi toteuttaa tämän yksinkertaisen menetelmän käyttämällä kolmea sisäkkäistä silmukkaa.

Vaiheittainen lähestymistapa:

• Annettu joukko pituus n ja summa s
• Luo kolme sisäkkäistä silmukkaa, ensimmäinen silmukka juoksee alusta loppuun (silmukkalaskuri i), toinen silmukka alkaa i+1 loppuun (silmukkalaskuri j) ja kolmas silmukka alkaa j+1 loppuun (silmukkalaskuri k)
• Näiden silmukoiden laskuri edustaa indeksiä 3 kolmosten elementtejä.
• Etsi i:nnen, j:nnen ja k:nnen elementin summa. Jos summa on yhtä suuri kuin annettu summa. Tulosta tripletti ja katkaise.
• Jos triplettiä ei ole, tulosta, ettei triplettiä ole.

Alla on yllä olevan lähestymistavan toteutus:

C++

>

>

C

>

>

Java

>

>

Python 3

>

>

C#

>

>

Javascript

>

>

PHP

> 
    
 Triplet is 4, 10, 8>

Monimutkaisuusanalyysi:

• Aika monimutkaisuus: Päällä³), Matriisin läpi kulkee kolme sisäkkäistä silmukkaa, joten aikamonimutkaisuus on O(n^3)
• Aputila: O(1), Koska lisätilaa ei tarvita.

Triplet Sum in Array (3sum) käyttämällä Kahden osoittimen tekniikka :

Lajittelemalla taulukkoa voidaan parantaa algoritmin tehokkuutta. Tämä tehokas lähestymistapa käyttää kahden osoittimen tekniikka . Kävele taulukko ja korjaa tripletin ensimmäinen elementti. Käytä nyt Two Pointers -algoritmia selvittääksesi, onko olemassa paria, jonka summa on yhtä suuri x – array[i] . Kahden osoittimen algoritmi vie lineaarisen ajan, joten se on parempi kuin sisäkkäinen silmukka.

Vaiheittainen lähestymistapa:

• Lajittele annettu matriisi.
• Kierrä taulukon yli ja korjaa mahdollisen tripletin ensimmäinen elementti, arr[i] .
• Korjaa sitten kaksi osoitinta, yksi kohdassa minä + 1 ja toinen klo n-1 . Ja katso summaa,
  • Jos summa on pienempi kuin vaadittu summa, lisää ensimmäistä osoitinta.
  • Muussa tapauksessa, jos summa on suurempi, pienennä loppuosoitinta summan pienentämiseksi.
  • Muuten, jos kahden osoittimen elementtien summa on yhtä suuri kuin annettu summa, tulosta tripletti ja katkaise.

Alla on yllä olevan lähestymistavan toteutus:

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] summa r -= 1 # Jos päästään tähän, niin # triplettiä ei löytynyt return False # Ajuriohjelma testattava yllä oleva funktio A = [1, 4, 45, 6, 10, 8] summa = 22 arr_size = len(A) find3Numbers(A, arr_size, sum) # Tämän on kirjoittanut Smitha Dinesh Semwal>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // 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--;  } } // Jos pääsemme tänne, // triplettiä ei löytynyt return false;  } int osio(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[] -->Lajiteltava taulukko si --> Alkuindeksi ei --> Loppuindeksi */ void quickSort(int[] A, int si, int ei) { int pi;  /* Osioindeksi */ if (si pi = osio(A, si, ei); quickSort(A, si, pi - 1); quickSort(A, pi + 1, ei); } } // Ohjainkoodi static void Main() { GFG-kolikko = new int[] A = uusi int[] { 1, 4, 45, 6, 10, 8 } int arr_size = A.Length; (A, arr_size, summa);
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 > // 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--;  } } // Jos pääsemme tänne, triplettiä ei löytynyt return false; } /* Ohjainohjelma testattava yllä oleva toiminto */ olkoon A = [ 1, 4, 45, 6, 10, 8 ];  olkoon summa = 22;  let arr_size = A.pituus;  find3Numbers(A, arr_size, summa); // Tämän koodin on toimittanut Mayank Tyagi>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
muuntaa int merkkijonoksi java
 
 
 
 
 
  // 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--;  } } // Jos pääsemme tänne, // triplettiä ei löytynyt return false; } // Ohjainkoodi $A = taulukko (1, 4, 45, 6, 10, 8); $summa = 22; $arr_size = koko($A); find3Numbers($A, $arr_size, $sum); // Tämän koodin tarjoaa ajit ?>>>
 
 
 
 
    
 
>
 
    
 
>
 
  Lähtö  
 
Triplet is 4, 8, 10>
 
    Monimutkaisuusanalyysi:     
 
 
    Aika monimutkaisuus:    O(N^2), Matriisin läpi kulkee vain kaksi sisäkkäistä silmukkaa, joten aikamonimutkaisuus on O(n^2). Kahden osoittimen algoritmi vie O(n) aikaa ja ensimmäinen elementti voidaan korjata käyttämällä toista sisäkkäistä läpikulkua.
 
    Aputila:    O(1), Koska lisätilaa ei tarvita.
 
 
    Triplet Sum in Array (3sum)    käyttämällä  Hashing  :
  
 
Tämä lähestymistapa käyttää ylimääräistä tilaa, mutta on yksinkertaisempi kuin kahden osoittimen lähestymistapa. Suorita kaksi silmukkaa ulompi silmukka alusta loppuun ja sisempi silmukka    i+1    Loppuun. Luo hashmap tai aseta tallentamaan elementit väliin    i+1    to    n-1    . Joten jos annettu summa on    x,    tarkista, onko joukossa numero, joka on yhtä suuri kuin    x         – arr[i] – arr[j]    . Jos kyllä, tulosta tripletti.
 
 
Vaiheittainen lähestymistapa:
 
 
Iteroi taulukon läpi ja kiinnitä ensimmäinen elementti (    A[i]    ) kolmoselle.
 
Jokaiselle    A[i]    , käytä Hashmappia         tallentaa mahdolliset toiset elementit, jotka täydentävät halutun summan    (summa – A[i])    .
 
Tarkista sisäkkäisen silmukan sisällä, onko ero nykyisen elementin (    A[j]    ) ja haluttu summa (    summa – A[i]    ) on mukana Hashmapissa. Jos on, tripletti löytyy ja tulosta se.
 
Jos triplettiä ei löydy koko taulukosta, funktio palauttaa    väärä    .
 
 
Alla on yllä olevan lähestymistavan toteutus:
 
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;  // Laske nykyinen summa, joka tarvitaan saavuttamaan // tavoitesumma int curr_sum = summa - A[i];  // Iteroi alitaulukkoa A[i+1..n-1] löytääksesi // pari, jolla on vaadittu summa (int j = i + 1; j // Laske vaadittava arvo toiselle // elementille int vaadittu_arvo = curr_sum - A[j] // Tarkista, onko vaadittu arvo mukana // joukossa if (s.find(required_value) != s.end()) { // Tripletti löytyy /; / elements printf('Tripletti on %d, %d, %d', A[i], A[j], return true } // Lisää nykyinen elementti joukkoon tulevaa varten tarkistaa s.insert(A[j]) // Jos triplettiä ei löydy, palauttaa false return false } /* Ohjainohjelma testatakseen yllä olevan funktion */ int main() { int A[] = { 1, 4, 45, 6, 10, 8 }; int arr_size = sizeof(A) / sizeof(A[0]) // Kutsu Find3Numbers-funktio, jos se on olemassa find3Numbers(A, arr_size, summa }>'>;
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 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.');  }  } }>
 
 
 
 
    
 
>
 
    
 
>
 
 
Python 3
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # 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 = uusi HashSet ();  // Laske nykyinen summa, joka tarvitaan saavuttamaan // tavoitesumma int curr_sum = summa - arr[i];  // Toista alitaulukko arr[i+1:] for (int j = i + 1; j // Laske vaadittu arvo // toiselle elementille int vaadittu_arvo = curr_sum - arr[j]; // Tarkista, onko vaadittu arvo on läsnä // HashSetissä if (s.Contains(required_value)) { // Tripletti löytyy tulostaa tripletti // elementit Console.WriteLine('Tripletti on ' + arr[i] + ', ' Jos triplettiä ei löydy, palauta false return false } // Ajuriohjelma, joka testaa Find3Numbers-funktion static void Main() { int[] arr = { 1, 4, 45, 6, 10, 8 }; ; // Kutsu3Nummers-funktio etsimään ja tulostamaan // tripletti, jos se on olemassa (!Find3Numbers(arr, target_sum)) { Console.WriteLine('Ei triplettiä löytynyt.' } } }>'>);
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 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();>
 
 
 
 
    
 
>
 
    
 
>
 
  Lähtö  
 
Triplet is 4, 8, 10>
 
    Aika monimutkaisuus:    O(N^2)  
    Aputila:    O(N), koska n ylimääräistä tilaa on otettu
 
Voit katsoa ongelman selityksen  YouTube  keskusteli Geeks For Geeks Team.
 
Voit myös viitata  Tämä  video esillä Youtubessa.  
    Kuinka tulostaa kaikki kolmoset annetulla summalla?       
Viitata Etsi kaikki kolmoset, joiden summa on nolla .