Gegeven een array arr[] van grootte N en een geheel getal X . Zoek of er een triplet in de array zit die optelt tot het gegeven gehele getal X .

Voorbeelden:

Invoer: array = {12, 3, 4, 1, 6, 9}, som = 24;
Uitgang: 12, 3, 9
Uitleg: Er is een triplet (12, 3 en 9) aanwezig
in de array waarvan de som 24 is.

Invoer: array = {1, 2, 3, 4, 5}, som = 9
Uitgang: 5, 3, 1
Uitleg: Er is een triplet (5, 3 en 1) aanwezig
in de array waarvan de som 9 is.

Tripletsom in array (3som) door alle tripletten te genereren:

Een eenvoudige methode is om alle mogelijke tripletten te genereren en de som van elke triplet te vergelijken met de gegeven waarde. De volgende code implementeert deze eenvoudige methode met behulp van drie geneste lussen.

Stapsgewijze aanpak:

• Gegeven een array van lengte N en een bedrag S
• Maak drie geneste lus, eerste lus loopt van begin tot eind (lusteller i), tweede lus loopt vanaf ik+1 eindigen (lusteller j) en de derde lus loopt vanaf j+1 eindigen (lusteller k)
• De teller van deze lussen vertegenwoordigt de index van 3 elementen van de drieling.
• Vind de som van het i-de, j-de en k-de element. Als de som gelijk is aan de gegeven som. Druk het triplet af en breek.
• Als er geen triplet is, druk dan af dat er geen triplet bestaat.

Hieronder vindt u de implementatie van de bovenstaande aanpak:

C++

>

>

C

vetgedrukt in css

>

>

Java

>

>

Python3

>

>

C#

>

>

Javascript

>

>

PHP

>

>

Triplet is 4, 10, 8>

Complexiteitsanalyse:

• Tijdcomplexiteit: Op³), Er lopen drie geneste lussen door de array, dus de tijdscomplexiteit is O(n^3)
• Hulpruimte: O(1), Omdat er geen extra ruimte nodig is.

Tripletsom in array (3som) gebruik makend van Tweepuntstechniek :

Door de array te sorteren kan de efficiëntie van het algoritme worden verbeterd. Deze efficiënte aanpak maakt gebruik van de tweepuntstechniek . Doorkruis de array en bevestig het eerste element van het triplet. Gebruik nu het Two Pointers-algoritme om te bepalen of er een paar is waarvan de som gelijk is aan x – array[i] . Het algoritme met twee wijzers heeft lineaire tijd nodig, dus het is beter dan een geneste lus.

Stapsgewijze aanpak:

• Sorteer de gegeven array.
• Loop over de array en bevestig het eerste element van het mogelijke triplet, arr[ik] .
• Bevestig vervolgens twee wijzers, één op ik + 1 en de andere bij n – 1 . En kijk naar de som,
  • Als de som kleiner is dan de vereiste som, verhoogt u de eerste aanwijzer.
  • Anders, als de som groter is, verlaag dan de eindaanwijzer om de som te verkleinen.
  • Anders, als de som van de elementen op de tweepunter gelijk is aan de gegeven som, druk dan het triplet af en breek.

Hieronder vindt u de implementatie van de bovenstaande aanpak:

C++

>

>

C

>

>

Java

> 
    
   
 
     
  
machine learning en typen
 
    
 
     
     
    
 
 
 
 
 
 # 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] som r -= 1 # Als we hier komen, dan # is er geen triplet gevonden return False # Stuurprogramma om bovenstaande functie te testen A = [1, 4, 45, 6, 10, 8] som = 22 arr_size = len(A) find3Numbers(A, arr_size, sum) # Dit is bijgedragen door 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]>som r--;  } } // Als we hier komen, // is er geen triplet gevonden return false;  } int partitie(int[] A, int si, int ei) { int x = A[ei];  int ik = (si - 1);  int j;  voor (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 die moet worden gesorteerd si --> Beginindex ei --> Eindindex */ void quickSort(int[] A, int si, int ei) { int pi;  /* Partitioneringsindex */ if (si pi = partitie(A, si, ei); quickSort(A, si, pi - 1); quickSort(A, pi + 1, ei); } } // Stuurprogrammacode static void Main() { GFG-triplet = nieuwe GFG(); A = nieuwe int[] { 1, 4, 45, 6, 10, 8 }; (A, arr_size, sum); } } // Deze code is bijgedragen door 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]>som r--;  } } // Als we hier komen, is er geen triplet gevonden return false; } /* Stuurprogramma om bovenstaande functie te testen */ let A = [ 1, 4, 45, 6, 10, 8 ];  laat som = 22;  laat arr_size = A.lengte;  find3Numbers(A, arr_size, som); // Deze code is bijgedragen door 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]>som $r--;  } } // Als we hier komen, // is er geen triplet gevonden return false; } // Stuurprogrammacode $A = array (1, 4, 45, 6, 10, 8); $som = 22; $arr_size = groottevan($A); find3Numbers($A, $arr_size, $sum); // Deze code is bijgedragen door ajit ?>>
 
 
 
 
    
 
>
 
    
 
>
 
  Uitvoer  
 
Triplet is 4, 8, 10>
 
    Complexiteitsanalyse:     
 
 
    Tijdcomplexiteit:    O(N^2), Er lopen slechts twee geneste lussen door de array, dus de tijdscomplexiteit is O(n^2). Het twee-wijzeralgoritme kost O(n) tijd en het eerste element kan worden opgelost met behulp van een andere geneste traversal.
 
    Hulpruimte:    O(1), Omdat er geen extra ruimte nodig is.
 
 
    Tripletsom in array (3som)    gebruik makend van  Hashing  :
  
 
Deze benadering gebruikt extra ruimte, maar is eenvoudiger dan de tweepuntsbenadering. Voer twee lussen uit, de buitenste lus van begin tot eind en de binnenste lus vanaf    ik+1    beëindigen. Maak een hashmap of set om de elementen ertussen op te slaan    ik+1    naar    n-1    . Dus als de gegeven som is    X,    controleer of er een getal in de set zit dat gelijk is aan    X         – arr[i] – arr[j]    . Zo ja, druk het triplet af.
 
 
Stapsgewijze aanpak:
 
 
Herhaal de array en repareer het eerste element (    EEN[ik]    ) voor het drietal.
 
Voor elk    EEN[ik]    , gebruik een Hashmap         om potentiële tweede elementen op te slaan die de gewenste som voltooien    (som – A[i])    .
 
Controleer binnen een geneste lus of het verschil tussen het huidige element (    A[j]    ) en het gewenste bedrag (    som – A[i]    ) is aanwezig in de Hashmap. Als dat zo is, wordt er een triplet gevonden en drukt u deze af.
 
Als er geen triplet wordt gevonden in de hele array, retourneert de functie    vals    .
 
 
Hieronder vindt u de implementatie van de bovenstaande aanpak:
 
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;  // Bereken de huidige som die nodig is om de // target sum int curr_sum = sum - A[i];  // Doorloop de subarray A[i+1..n-1] om // een paar te vinden met de vereiste som voor (int j = i + 1; j // Bereken de vereiste waarde voor het tweede // element int require_value = curr_sum - A[j]; // Controleer of de vereiste waarde aanwezig is in // set if (s.find(required_value) != s.end()) {// Triplet is gevonden; / elements printf('Triplet is %d, %d, %d', A[i], A[j], vereiste_waarde true } // Voeg het huidige element toe aan de set voor toekomstig // complement; checks s.insert(A[j]); } } // Als er geen triplet wordt gevonden, retourneert false return false } /* Stuurprogramma om bovenstaande functie te testen */ int main() { int A[] = { 1, 4, 45, 6, 10, 8 }; int sum = 22; int arr_size = sizeof(A) / sizeof(A[0]); // Roep de functie find3Numbers aan om het // triplet te vinden en af ​​te drukken, als dit bestaat find3Numbers(A, arr_size, som); retourneert 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 = nieuwe HashSet ();  // Bereken de huidige som die nodig is om de // target sum int curr_sum = sum - arr[i] te bereiken;  // Doorloop de subarray arr[i+1:] for (int j = i + 1; j // Bereken de vereiste waarde voor // tweede element int require_value = curr_sum - arr[j]; // Controleer of de vereiste waarde is aanwezig in // de HashSet if (s.Contains(required_value)) {// Triplet is gevonden; print het triplet // elements Console.WriteLine('Triplet is ' + arr[i] + ', ' + arr[j] + ', ' + vereiste_waarde); return true; } // Voeg het huidige element toe aan de HashSet // voor toekomstige complementcontroles s.Add(arr[j]); Als er geen triplet wordt gevonden, retourneer false return false } // Stuurprogramma om de Find3Numbers-functie te testen static void Main() { int[] arr = { 1, 4, 45, 6, 10, 8 }; ; // Roep de Find3Numbers-functie aan om // het triplet te vinden en af ​​te drukken, als het bestaat if (!Find3Numbers(arr, target_sum)) { Console.WriteLine('Geen triplet gevonden.'>).
 
 
 
 
    
 
> 
    
   
typoscript datum
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 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();>
 
 
 
 
    
 
>
 
    
 
>
 
  Uitvoer  
 
Triplet is 4, 8, 10>
 
    Tijdcomplexiteit:    O(N^2)  
    Hulpruimte:    O(N), omdat er n extra ruimte is ingenomen
 
De uitleg van het probleem kunt u bekijken op  YouTube  besproken door Geeks voor het Geeks-team.
 
U kunt ook verwijzen  dit  video aanwezig op Youtube.  
    Hoe print ik alle drielingen met een bepaalde som?       
Refereren Vind alle drielingen met nulsom .