Étant donné un tableau arr[] de taille n et un entier X . Rechercher s'il y a un triplet dans le tableau qui résume l'entier donné X .

Exemples:

Saisir: tableau = {12, 3, 4, 1, 6, 9}, somme = 24 ;
Sortir: 12, 3, 9
Explication: Il y a un triplet (12, 3 et 9) présent
dans le tableau dont la somme est 24.

Saisir: tableau = {1, 2, 3, 4, 5}, somme = 9
Sortir: 5, 3, 1
Explication: Il y a un triplet (5, 3 et 1) présent
dans le tableau dont la somme est 9.

Somme triplet dans un tableau (3sum) en générant tous les triplets :

Une méthode simple consiste à générer tous les triplets possibles et à comparer la somme de chaque triplet avec la valeur donnée. Le code suivant implémente cette méthode simple en utilisant trois boucles imbriquées.

Approche étape par étape :

• Étant donné un tableau de longueur n et une somme s
• Créez trois boucles imbriquées, la première boucle s'exécute du début à la fin (compteur de boucle i), la deuxième boucle s'exécute à partir de je+1 pour terminer (compteur de boucle j) et la troisième boucle part de j+1 terminer (compteur de boucle k)
• Le compteur de ces boucles représente l'indice de 3 éléments des triplés.
• Trouvez la somme des ième, jième et kième éléments. Si la somme est égale à la somme donnée. Imprimez le triplet et cassez.
• S'il n'y a pas de triplet, affichez qu'aucun triplet n'existe.

Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :

C++

liste de fléchettes

>

>

C

>

>

Java

>

>

Python3

>

>

C#

>

>

Javascript

>

>

PHP

fourmi contre maven

>

>

Triplet is 4, 10, 8>

Analyse de complexité :

• Complexité temporelle : Sur³), Il y a trois boucles imbriquées traversant le tableau, donc la complexité temporelle est O(n^3)
• Espace auxiliaire : O(1), car aucun espace supplémentaire n'est requis.

Somme triplet dans un tableau (3sum) en utilisant Technique à deux pointeurs :

En triant le tableau, l'efficacité de l'algorithme peut être améliorée. Cette approche efficace utilise le technique à deux points . Parcourez le tableau et corrigez le premier élément du triplet. Utilisez maintenant l’algorithme Two Pointers pour déterminer s’il existe une paire dont la somme est égale à x – tableau[i] . L'algorithme à deux pointeurs prend un temps linéaire, c'est donc mieux qu'une boucle imbriquée.

Approche étape par étape :

• Trie le tableau donné.
• Bouclez sur le tableau et fixez le premier élément du triplet possible, arr[je] .
• Fixez ensuite deux pointeurs, un sur je + 1 et l'autre à n – 1 . Et regarde la somme,
  • Si la somme est inférieure à la somme requise, incrémentez le premier pointeur.
  • Sinon, si la somme est plus grande, diminuez le pointeur de fin pour réduire la somme.
  • Sinon, si la somme des éléments à deux pointeurs est égale à la somme donnée, imprimez le triplet et rompez.

Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :

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 # Si nous arrivons ici, alors # aucun triplet n'a été trouvé return False # Programme pilote pour tester la fonction ci-dessus A = [1, 4, 45, 6, 10, 8] sum = 22 arr_size = len(A) find3Numbers(A, arr_size, sum) # Ceci est une contribution de 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]>somme r-- ;  } } // Si nous arrivons ici, alors // aucun triplet n'a été trouvé return false;  } int partition(int[] A, int si, int ei) { int x = A[ei];  int je = (si - 1);  int j;  pour (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[] -->Tableau à trier si --> Index de début ei --> Index de fin */ void quickSort(int[] A, int si, int ei) { int pi;  /* Indice de partitionnement */ if (si pi = partition(A, si, ei); quickSort(A, si, pi - 1); quickSort(A, pi + 1, ei); } } // Driver Code static void Main() { GFG triplet = new GFG(); int[] A = new int[] { 1, 4, 45, 6, 10, 8 }; int arr_size = A.Length triplet.find3Numbers; (A, arr_size, sum); } } // Ce code est contribué par 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]>somme r-- ;  } } // Si nous arrivons ici, alors aucun triplet n'a été trouvé return false; } /* Programme pilote pour tester la fonction ci-dessus */ let A = [ 1, 4, 45, 6, 10, 8 ];  soit somme = 22 ;  soit arr_size = A.length;  find3Numbers(A, arr_size, somme); // Ce code est contribué par Mayank Tyagi>
 
 
 
 
conversion de chaîne Java en entier
    
 
>
 
    
 
>
 
 
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]>somme $r--;  } } // Si nous arrivons ici, alors // aucun triplet n'a été trouvé return false; } // Code du pilote $A = tableau (1, 4, 45, 6, 10, 8) ; Somme $ = 22 ; $arr_size = taillede($A); find3Numbers($A, $arr_size, $sum); // Ce code est contribué par ajit ?>>
 
 
 
 
    
 
>
 
    
 
>
 
  Sortir  
 
Triplet is 4, 8, 10>
 
    Analyse de complexité :     
 
 
    Complexité temporelle :    O(N^2), il n'y a que deux boucles imbriquées traversant le tableau, donc la complexité temporelle est O(n^2). L'algorithme à deux pointeurs prend un temps O(n) et le premier élément peut être corrigé à l'aide d'un autre parcours imbriqué.
 
    Espace auxiliaire :    O(1), car aucun espace supplémentaire n'est requis.
 
 
    Somme triplet dans un tableau (3sum)    en utilisant  Hachage  :
  
 
Cette approche utilise de l'espace supplémentaire mais est plus simple que l'approche à deux pointeurs. Exécutez deux boucles externes du début à la fin et une boucle interne de    je+1    finir. Créez une table de hachage ou un ensemble pour stocker les éléments intermédiaires    je+1    à    n-1    . Donc si la somme donnée est    X,    vérifier s'il y a un nombre dans l'ensemble qui est égal à    X         – arr[je] – arr[j]    . Si oui, imprimez le triplet.
 
 
Approche étape par étape :
 
 
Parcourez le tableau en corrigeant le premier élément (    UNE[je]    ) pour le triplet.
 
Pour chaque    UNE[je]    , utilisez un Hashmap         pour stocker des seconds éléments potentiels qui complètent la somme souhaitée    (somme – A[i])    .
 
Dans une boucle imbriquée, vérifiez si la différence entre l'élément actuel (    A[j]    ) et la somme souhaitée (    somme – A[i]    ) est présent dans le Hashmap. Si c'est le cas, un triplet est trouvé, alors imprimez-le.
 
Si aucun triplet n'est trouvé dans l'ensemble du tableau, la fonction renvoie    FAUX    .
 
 
Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :
 
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 ;  // Calcule la somme actuelle nécessaire pour atteindre // la somme cible int curr_sum = sum - A[i];  // Parcourez le sous-tableau A[i+1..n-1] pour trouver // une paire avec la somme requise pour (int j = i + 1; j // Calculez la valeur requise pour le deuxième // élément int require_value = curr_sum - A[j]; // Vérifiez si la valeur requise est présente dans le // set if (s.find(required_value) != s.end()) { // affiche le triplet / / elements printf('Le triplet est %d, %d, %d', A[i], A[j], require_value); return true } // Ajoute l'élément actuel à l'ensemble pour // le futur complément ; checks s.insert(A[j]); } } // Si aucun triplet n'est trouvé, return false return false } /* Programme pilote pour tester la fonction ci-dessus */ int main() { int A[] = { 1, 4, 45, 6, 10, 8 }; int sum = 22; int arr_size = sizeof(A) / sizeof(A[0]); // Appelez la fonction find3Numbers pour rechercher et imprimer le // triplet, s'il existe find3Numbers(A, arr_size, somme); return 0;
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
Java statique
 
 
 
 
 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 = nouveau HashSet ();  // Calcule la somme actuelle nécessaire pour atteindre // la somme cible int curr_sum = sum - arr[i];  // Parcourez le sous-tableau arr[i+1:] for (int j = i + 1; j // Calculez la valeur requise pour le // deuxième élément int require_value = curr_sum - arr[j]; // Vérifiez si le la valeur requise est présente dans // le HashSet if (s.Contains(required_value)) { // Le triplet est trouvé ; affiche le triplet // éléments Console.WriteLine('Triplet is ' + arr[i] + ', ' + arr[j] + ', ' + require_value); return true; } // Ajoute l'élément actuel au HashSet // pour les futures vérifications de complément s.Add(arr[j]); Si aucun triplet n'est trouvé, return false return false; } // Programme pilote pour tester la fonction Find3Numbers static void Main() { int[] arr = { 1, 4, 45, 6, 10, 8 }; ; // Appelez la fonction Find3Numbers pour rechercher et imprimer // le triplet, s'il existe if (!Find3Numbers(arr, target_sum)) { Console.WriteLine('Aucun triplet trouvé.');
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 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();>
 
 
 
 
    
 
>
 
    
 
>
 
  Sortir  
 
Triplet is 4, 8, 10>
 
    Complexité temporelle :    O(N^2)  
    Espace auxiliaire :    O(N), puisque n espace supplémentaire a été pris
 
Vous pouvez regarder l'explication du problème sur  Youtube  discuté par l’équipe Geeks For Geeks.
 
Vous pouvez également vous référer  ce  vidéo présente sur Youtube.  
    Comment imprimer tous les triplets avec une somme donnée ?       
Référer Trouver tous les triplets à somme nulle .