Dots masīvs arr[] izmēra n un vesels skaitlis X . Atrodiet, vai masīvā ir triplets, kas summējas ar doto veselo skaitli X .

Piemēri:

Ievade: masīvs = {12, 3, 4, 1, 6, 9}, summa = 24;
Izvade: 12, 3, 9
Paskaidrojums: Ir klāt trīnīši (12, 3 un 9).
masīvā, kuras summa ir 24.

Ievade: masīvs = {1, 2, 3, 4, 5}, summa = 9
Izvade: 5, 3, 1
Paskaidrojums: Klāt ir trīskāršs (5, 3 un 1).
masīvā, kuras summa ir 9.

Trīskāršu summa masīvā (3 summas) ģenerējot visus trīskāršus:

Vienkārša metode ir ģenerēt visus iespējamos tripletus un salīdzināt katra tripleta summu ar doto vērtību. Šis kods ievieš šo vienkāršo metodi, izmantojot trīs ligzdotas cilpas.

Soli pa solim pieeja:

• Dots garuma masīvs n un summa s
• Izveidojiet trīs ligzdotas cilpas pirmās cilpas darbības no sākuma līdz beigām (cilpas skaitītājs i), otrā cilpa darbojas no i+1 līdz beigām (cilpas skaitītājs j) un trešā cilpa sākas no j+1 līdz beigām (cilpas skaitītājs k)
• Šo cilpu skaitītājs apzīmē indeksu 3 tripletu elementi.
• Atrodiet ith, jth un kth elementu summu. Ja summa ir vienāda ar doto summu. Izdrukājiet tripletu un pārtrauciet.
• Ja nav tripleta, izdrukājiet, ka tripleta nav.

Tālāk ir aprakstīta iepriekš minētās pieejas īstenošana.

C++

>

>

C

>

>

Java

>

>

Python3

sed komanda

>

>

C#

>

>

Javascript

>

>

PHP

> 
    
 Triplet is 4, 10, 8>

Sarežģītības analīze:

• Laika sarežģītība: O(n³), Masīvu šķērso trīs ligzdotas cilpas, tāpēc laika sarežģītība ir O(n^3)
• Palīgtelpa: O(1), jo nav nepieciešama papildu vieta.

Trīskāršu summa masīvā (3 summas) izmantojot Divu rādītāju tehnika :

Kārtojot masīvu, var uzlabot algoritma efektivitāti. Šī efektīva pieeja izmanto divpunktnieku tehnika . Šķērsojiet masīvu un nofiksējiet pirmo tripleta elementu. Tagad izmantojiet divu rādītāju algoritmu, lai noskaidrotu, vai ir pāris, kura summa ir vienāda ar x — masīvs[i] . Divu rādītāju algoritmam ir nepieciešams lineārs laiks, tāpēc tas ir labāks par ligzdotu cilpu.

Soli pa solim pieeja:

• Kārtot doto masīvu.
• Apgrieziet masīvu un nofiksējiet iespējamā tripleta pirmo elementu, arr[i] .
• Pēc tam nofiksējiet divus rādītājus, vienu pie i + 1 un otrs plkst n-1 . Un paskaties uz summu,
  • Ja summa ir mazāka par nepieciešamo summu, palieliniet pirmo rādītāju.
  • Citādi, ja summa ir lielāka, samaziniet beigu rādītāju, lai samazinātu summu.
  • Citādi, ja elementu summa divos rādītājā ir vienāda ar doto summu, izdrukā tripletu un pārtrauc.

Tālāk ir aprakstīta iepriekš minētās pieejas īstenošana.

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 # Ja mēs sasniedzam šeit, tad # netika atrasts neviens triplets return False # Draiverprogramma, lai pārbaudītu iepriekš minēto funkciju A = [1, 4, 45, 6, 10, 8] summa = 22 arr_size = len(A) find3Numbers(A, arr_size, sum) # To sniedza Smita 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--;  } } // Ja mēs sasniedzam šeit, tad // triplets netika atrasts 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[] -->Kārtojamais masīvs si --> Sākuma indekss ei --> Beigu indekss */ void quickSort(int[] A, int si, int ei) { int pi;  /* Sadalīšanas indekss */ if (si pi = partition(A, si, ei); quickSort(A, si, pi - 1); quickSort(A, pi + 1, ei); } } // Draivera koda statisks spēkā neesošs Main() { GFG triplets = new int[] A = new int[] { 1, 4, 45, 6, 10, 8 } int arr_size = A.Length; (A, arr_size, summa) } } // Šo kodu nodrošina 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]>summa r--;  } } // Ja mēs sasniedzam šeit, tad neviens triplets netika atrasts return false; } /* Draivera programma, lai pārbaudītu iepriekšminēto funkciju */ lai A = [ 1, 4, 45, 6, 10, 8 ];  pieņemsim, ka summa = 22;  let arr_size = A.garums;  atrast3 Skaitļi(A, arr_size, summa); // Šo kodu ir sagatavojis 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--;  } } // Ja mēs sasniedzam šeit, tad // triplets netika atrasts return false; } // Draivera kods $A = masīvs (1, 4, 45, 6, 10, 8); $ summa = 22; $arr_size = izmērs($A); atrast3Cipari($A, $arr_size, $sum); // Šo kodu ir sagatavojis ajit ?>>
 
 
 
 
    
 
>
 
    
 
>
 
  Izvade  
 
Triplet is 4, 8, 10>
 
    Sarežģītības analīze:     
 
 
    Laika sarežģītība:    O(N^2), Masīvu šķērso tikai divas ligzdotas cilpas, tāpēc laika sarežģītība ir O(n^2). Divu rādītāju algoritmam nepieciešams O(n) laiks, un pirmo elementu var salabot, izmantojot citu ligzdotu šķērsošanu.
 
    Palīgtelpa:    O(1), jo nav nepieciešama papildu vieta.
 
 
    Trīskāršu summa masīvā (3 summas)    izmantojot  Jaukšana  :
  
 
Šī pieeja izmanto papildu vietu, taču ir vienkāršāka nekā divu rādītāju pieeja. Palaidiet divas cilpas ārējo cilpu no sākuma līdz beigām un iekšējo cilpu no    i+1    līdz beigām. Izveidojiet hashmap vai iestatījumu, lai saglabātu elementus starp tiem    i+1    uz    n-1    . Tātad, ja dotā summa ir    x,    pārbaudiet, vai komplektā ir skaitlis, kas ir vienāds ar    x         – arr[i] – arr[j]    . Ja jā, izdrukājiet tripletu.
 
 
Soli pa solim pieeja:
 
 
Atkārtojiet masīvu, fiksējot pirmo elementu (    A[i]    ) par trīni.
 
Katram    A[i]    , izmantojiet Hashmap         lai saglabātu potenciālos otros elementus, kas papildina vēlamo summu    (summa — A[i])    .
 
Ligzdotas cilpas iekšpusē pārbaudiet, vai nav atšķirības starp pašreizējo elementu (    A[j]    ) un vēlamo summu (    summa – A[i]    ) atrodas Hashmapā. Ja tā ir, tiek atrasts triplets, tad izdrukājiet to.
 
Ja visā masīvā netiek atrasts neviens triplets, funkcija atgriežas    viltus    .
 
 
Tālāk ir aprakstīta iepriekš minētās pieejas īstenošana.
 
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;  // Aprēķināt pašreizējo summu, kas nepieciešama, lai sasniegtu // mērķa summu int curr_sum = summa - A[i];  // Atkārtojiet caur apakšgrupu A[i+1..n-1], lai atrastu // pāri ar nepieciešamo summu priekš (int j = i + 1; j // Aprēķiniet nepieciešamo vērtību otrajam // elementam int Nepieciešamā_vērtība = curr_sum - A[j] // Pārbaudiet, vai vajadzīgā vērtība ir // komplektā if (s.find(required_value) != s.end()) { // Triplets ir atrasts /; / elements printf('Triplets ir %d, %d, %d', A[i], A[j], atgriež true } // Pievienot pašreizējo elementu kopai nākotnei // papildināt); pārbauda s.insert(A[j]) // Ja nav atrasts triplets, atgriež false return false } /* Draiveri, lai pārbaudītu iepriekš minēto funkciju */ int main() { int A[] = { 1, 4, 45, 6, 10, 8 }; int arr_size = sizeof(A) / sizeof(A[0]) // Izsauciet funkciju find3Numbers, lai atrastu un izdrukātu // tripletu 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.');  }  } }>
 
 
 
 
    
 
>
 
    
 
>
 
 
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 = jauns HashSet ();  // Aprēķināt pašreizējo summu, kas nepieciešama, lai sasniegtu // mērķa summu int curr_sum = summa - arr[i];  // Atkārtojiet, izmantojot apakšmasu arr[i+1:] for (int j = i + 1; j // Aprēķiniet nepieciešamo vērtību // otrajam elementam int required_value = curr_sum - arr[j]; // Pārbaudiet, vai vajadzīgā vērtība ir // HashSet if (s.Contains(required_value)) { // Triplets ir atrasts drukāt tripletu // elements Console.WriteLine('Triplet ir ' + arr[i] + ', ' + arr[j] + ', ' + nepieciešamā_vērtība atgriež true } // Pievienot pašreizējo elementu HashSet turpmākajām komplementa pārbaudēm } } //; Ja netiek atrasts neviens triplets, atgriež false return false } // Draivera programma, lai pārbaudītu funkciju Find3Numbers static void Main() { int[] arr = { 1, 4, 45, 6, 10, 8 }; // Izsauciet funkciju Find3Numbers, lai atrastu un izdrukātu // tripletu, ja tas pastāv (!Find3Numbers(arr, target_sum)) { Console.WriteLine('Nav atrasts triplets.' } } }>'>).
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 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();>
 
 
 
 
    
 
>
 
    
 
>
 
  Izvade  
 
Triplet is 4, 8, 10>
 
    Laika sarežģītība:    O(N^2)  
    Palīgtelpa:    O(N), jo ir aizņemta n papildu vieta
 
Jūs varat skatīties problēmas skaidrojumu  YouTube  apsprieda Geeks For Geeks Team.
 
Varat arī atsaukties  šis  video pieejams vietnē Youtube.  
    Kā izdrukāt visus tripletus ar norādīto summu?       
Atsaukties Atrodiet visus trīskāršus ar nulles summu .