Duotas masyvas arr[] dydžio n ir sveikasis skaičius X . Raskite, ar masyve yra tripletas, kuris susumuoja iki nurodyto sveikojo skaičiaus X .

Pavyzdžiai:

Įvestis: masyvas = {12, 3, 4, 1, 6, 9}, suma = 24;
Išvestis: 12, 3, 9
Paaiškinimas: Yra trynukas (12, 3 ir 9).
masyve, kurio suma lygi 24.

Įvestis: masyvas = {1, 2, 3, 4, 5}, suma = 9
Išvestis: 5, 3, 1
Paaiškinimas: Yra trynukas (5, 3 ir 1).
masyve, kurio suma lygi 9.

Triguba suma masyve (3 sumos) generuojant visus trynukus:

Paprastas būdas yra sugeneruoti visus įmanomus tripletus ir palyginti kiekvieno tripleto sumą su nurodyta reikšme. Šis kodas įgyvendina šį paprastą metodą, naudodamas tris įdėtas kilpas.

Žingsnis po žingsnio metodas:

• Pateiktas ilgio masyvas n ir suma s
• Sukurkite tris įdėtas kilpas, pirmoji kilpa paleidžiama nuo pradžios iki pabaigos (ciklų skaitiklis i), antrasis ciklas veikia nuo aš+1 iki pabaigos (ciklo skaitiklis j) ir trečioji kilpa eina nuo j+1 iki pabaigos (ciklų skaitiklis k)
• Šių kilpų skaitiklis rodo indeksą 3 trynukų elementai.
• Raskite i-ojo, j-ojo ir k-ojo elementų sumą. Jei suma lygi duotai sumai. Atspausdinkite tripletą ir sulaužykite.
• Jei nėra tripleto, tada atspausdinkite, kad nėra tripleto.

Toliau pateikiamas pirmiau minėto metodo įgyvendinimas:

C++

>

>

C

>

>

Java

>

>

Python3

>

>

C#

>

>

Javascript

>

>

PHP

stygų skaidymas c++

> 
    
 Triplet is 4, 10, 8>

Sudėtingumo analizė:

• Laiko sudėtingumas: O (n³), Yra trys įdėtos kilpos, kertančios masyvą, todėl laiko sudėtingumas yra O(n^3)
• Pagalbinė erdvė: O(1), nes nereikia papildomos vietos.

Triguba suma masyve (3 sumos) naudojant Dviejų rodyklių technika :

Rūšiuojant masyvą galima pagerinti algoritmo efektyvumą. Šis efektyvus metodas naudoja dvitaškio technika . Pereikite masyvą ir pataisykite pirmąjį tripleto elementą. Dabar naudokite dviejų rodyklių algoritmą, kad sužinotumėte, ar yra pora, kurios suma yra lygi x – masyvas[i] . Dviejų rodyklių algoritmui reikia linijinio laiko, todėl tai yra geriau nei įdėta kilpa.

Žingsnis po žingsnio metodas:

• Rūšiuoti pateiktą masyvą.
• Apsukite masyvą ir pataisykite pirmąjį galimo tripleto elementą, arr[i] .
• Tada pataisykite du rodiklius, vieną ties aš + 1 o kitas prie n – 1 . Ir pažiūrėk į sumą,
  • Jei suma mažesnė už reikalaujamą sumą, padidinkite pirmąją rodyklę.
  • Kitu atveju, jei suma yra didesnė, sumažinkite pabaigos žymeklį, kad sumažintumėte sumą.
  • Priešingu atveju, jei elementų suma dvitaškyje yra lygi nurodytai sumai, atspausdinkite tripletą ir pertraukite.

Toliau pateikiamas pirmiau minėto metodo įgyvendinimas:

C++

> 
    
   
 
     
  
diskrečiosios matematikos neigimas
 
    
 
     
     
    
 
 
 
 
 
 // C program to find a triplet> #include> #include> #include> int> cmpfunc(>const> void>* a,>const> void>* b)> {> >return> (*(>int>*)a - *(>int>*)b);> }> // 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 */> >qsort>(A, arr_size,>sizeof>(>int>), cmpfunc);> > >/* 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) {  printf('Triplet is %d, %d, %d', A[i], A[l],  A[r]);  return true;  }  else if (A[i] + A[l] + A[r]   l++;  else // A[i] + A[l] + A[r]>suma r--;  } } // Jei pasieksime čia, tai nerastas nė vienas trynukas return false; } /* Tvarkyklės programa, skirta patikrinti aukščiau pateiktą funkciją */ int main() { int A[] = { 1, 4, 45, 6, 10, 8 };  tarpinė suma = 22;  int arr_size = dydis(A) / dydis(A[0]);  rasti3Skaiciai(A, arr_dydis, suma);  grąžinti 0; } // Šį kodą sukūrė Aditya Kumar (adityakumar129)>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // Java program to find a triplet> class> FindTriplet {> >// returns true if there is triplet with sum equal> >// to 'sum' present in A[]. Also, prints the triplet> >boolean> 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 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  r = arr_size - 1; // index of the last element  while (l   if (A[i] + A[l] + A[r] == sum) {  System.out.print('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]>suma r--;  } } // Jei pasieksime čia, tai nerastas nė vienas trynukas return false;  } int skaidinys(int A[], int si, int ei) { int x = A[ei];  int i = (si - 1);  int j;  už (j = si; j<= ei - 1; j++) {  if (A[j] <= x) {  i++;  int temp = A[i];  A[i] = A[j];  A[j] = temp;  }  }  int temp = A[i + 1];  A[i + 1] = A[ei];  A[ei] = temp;  return (i + 1);  }  /* Implementation of Quick Sort  A[] -->Rūšiuotinas masyvas si --> Pradinis indeksas ei --> Pabaigos indeksas */ void quickSort(int A[], int si, int ei) { int pi;  /* Skirstymo indeksas */ if (si pi = skaidinys(A, si, ei); quickSort(A, si, pi - 1); quickSort(A, pi + 1, ei); } } // Tvarkyklės programa, kurią reikia išbandyti aukščiau esančios funkcijos public static void main(String[] args) { FindTripletas = new Int A[] = { 1, 4, 45, 6, 10, 8 } int arr_size = A; ilgis.find3Skaičiai(A, arr_dydis, suma } }>'>);
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # 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 # Jei pasieksime čia, tada # nerastas tripletas return False # Tvarkyklės programa, kurią reikia patikrinti aukščiau nurodyta funkcija A = [1, 4, 45, 6, 10, 8] suma = 22 arr_size = len(A) find3Numbers(A, arr_size, sum) # Tai pateikė 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]>suma r--;  } } // Jei pasieksime čia, tada // nebuvo rastas nė vienas trynukas return false;  } int skirsnis(int[] A, int si, int ei) { int x = A[ei];  int i = (si - 1);  int j;  už (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[] -->Rūšiuotinas masyvas si --> Pradinis indeksas ei --> Pabaigos indeksas */ void quickSort(int[] A, int si, int ei) { int pi;  /* Skirstymo indeksas */ if (si pi = skaidinys(A, si, ei); quickSort(A, si, pi - 1); quickSort(A, pi + 1, ei); } } // Tvarkyklės kodas statinis tuščias Main() { GFG tripletas = new int[] A = new int[] { 1, 4, 45, 6, 10, 8 } int arr_size = A. Tripletas (A, arr_size, suma);
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 > // 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]>suma r--;  } } // Jei pasieksime čia, tai nerastas nė vienas trynukas return false; } /* Tvarkyklės programa, skirta patikrinti aukščiau pateiktą funkciją */ tegul A = [ 1, 4, 45, 6, 10, 8 ];  tegul suma = 22;  tegul arr_size = A.ilgis;  rasti3Skaiciai(A, arr_dydis, suma); // Šį kodą sukūrė Mayank Tyagi>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
  // 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]>suma $r--;  } } // Jei pasieksime čia, tada // nebuvo rastas nė vienas trynukas return false; } // Tvarkyklės kodas $A = masyvas (1, 4, 45, 6, 10, 8); $ suma = 22; $arr_size = dydis($A); rasti3Skaiciai($A, $arr_dydis, $suma); // Šį kodą sukūrė ajit ?>>>
 
 
 
 
    
 
> 
    
 Triplet is 4, 8, 10>
 
    Sudėtingumo analizė:     
 
 
    Laiko sudėtingumas:    O(N^2), masyvą kerta tik dvi įdėtos kilpos, todėl laiko sudėtingumas yra O(n^2). Dviejų rodyklių algoritmas užtrunka O (n) laiko, o pirmasis elementas gali būti pataisytas naudojant kitą įdėtą perėjimą.
 
    Pagalbinė erdvė:    O(1), nes nereikia papildomos vietos.
 
 
    Triguba suma masyve (3 sumos)    naudojant  Maiša  :
  
 
Šis metodas užima daugiau vietos, bet yra paprastesnis nei dviejų žymeklių metodas. Vykdykite dviejų kilpų išorinę kilpą nuo pradžios iki pabaigos ir vidinę kilpą nuo    aš+1    baigti. Sukurkite maišos diagramą arba rinkinį, kad išsaugotumėte elementus tarp jų    aš+1    į    n-1    . Taigi, jei nurodyta suma yra    x,    patikrinkite, ar rinkinyje yra skaičius, kuris yra lygus    x         – arr[i] – arr[j]    . Jei taip, atspausdinkite tripletą.
 
 
Žingsnis po žingsnio metodas:
 
 
Pakartokite masyvą, nustatydami pirmąjį elementą (    A[i]    ) trejetukui.
 
Kiekvienam    A[i]    , naudokite Hashmap         saugoti potencialius antruosius elementus, kurie užbaigia norimą sumą    (suma – A[i])    .
 
Įdėtoje kilpoje patikrinkite, ar skirtumas tarp dabartinio elemento (    A[j]    ) ir norima suma (    suma – A[i]    ) yra Hashmap. Jei taip, randamas trynukas, tada jį atspausdinkite.
 
Jei visame masyve nerandamas tripletas, funkcija grąžinama    klaidinga    .
 
 
Toliau pateikiamas pirmiau minėto metodo įgyvendinimas:
 
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;  // Apskaičiuokite esamą sumą, reikalingą pasiekti // tikslinę sumą int curr_sum = suma - A[i];  // Pakartokite per pogrupį A[i+1..n-1], kad surastumėte // porą su reikiama suma (int j = i + 1; j // Apskaičiuokite reikiamą antrojo // elemento reikšmę int Reikalinga_vertė = curr_sum - A[j] // Patikrinkite, ar reikiama reikšmė yra // rinkinyje if (s.find(required_value) != s.end()) { // rastas tripletas /; / elements printf('Trejetas yra %d, %d, %d', A[i], A[j], reikalinga_reikšmė } // Pridėkite esamą elementą į rinkinį būsimam // papildymui); patikrina s.insert(A[j]); 4, 45, 6, 10, 8 }; int sum = 22; find3Skaičiai(A, arr_size, sum }>'>);
 
 
 
 
    
 
> 
    
   
kaip rodyti programos slėpimą „Android“.
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 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 = naujas maišos rinkinys ();  // Apskaičiuokite esamą sumą, reikalingą pasiekti // tikslinę sumą int curr_sum = sum - arr[i];  // Pakartokite per pogrupį arr[i+1:] for (int j = i + 1; j // Apskaičiuokite reikiamą // antrojo elemento reikšmę int reikalinga_vertė = curr_sum - arr[j]; // Patikrinkite, ar Reikalinga reikšmė yra // HashSet if (s.Contains(required_value)) { // Tripletas rastas spausdinti tripletą // elementai Console.WriteLine('Tripletas yra ' + arr[i] + ', ' + arr[j] + ', ' + Reikalinga_vertė Jei nerastas tripletas, grąžinkite false return false } // Tvarkyklės programa, skirta funkcijai Find3Numbs patikrinti static void Main() { int[] arr = { 1, 4, 45, 6, 10, 8 }; ; // Iškvieskite funkciją Find3Numbers, kad surastumėte ir išspausdintumėte // tripletą, jei jis yra (!Find3Numbers(arr, target_sum)) { Console.WriteLine('Nerastas tripletas.') } }>'>;
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 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();>
 
 
 
 
    
 
>
 
    
 
>
 
  Išvestis  
 
Triplet is 4, 8, 10>
 
    Laiko sudėtingumas:    O(N^2)  
    Pagalbinė erdvė:    O(N), nes buvo užimta n papildomos vietos
 
Galite žiūrėti problemos paaiškinimą  YouTube  aptarė Geeks For Geeks Team.
 
Taip pat galite kreiptis  tai  vaizdo įrašas pateikiamas Youtube.  
    Kaip atspausdinti visus trynukus su nurodyta suma?       
Nurodykite Raskite visus trynukus su nuline suma .