Gegeben ein Array arr[] der Größe N und eine ganze Zahl X . Finden Sie heraus, ob es im Array ein Triplett gibt, dessen Summe die angegebene ganze Zahl ergibt X .

Beispiele:

Eingang: Array = {12, 3, 4, 1, 6, 9}, Summe = 24;
Ausgabe: 12, 3, 9
Erläuterung: Es ist ein Triplett (12, 3 und 9) vorhanden
im Array, dessen Summe 24 ist.

Eingang: Array = {1, 2, 3, 4, 5}, Summe = 9
Ausgabe: 5, 3, 1
Erläuterung: Es ist ein Triplett (5, 3 und 1) vorhanden
im Array, dessen Summe 9 ist.

Triplettsumme im Array (3sum) durch Erzeugen aller Tripletts:

Eine einfache Methode besteht darin, alle möglichen Tripletts zu generieren und die Summe jedes Tripletts mit dem angegebenen Wert zu vergleichen. Der folgende Code implementiert diese einfache Methode mithilfe von drei verschachtelten Schleifen.

Schritt-für-Schritt-Ansatz:

• Gegeben ist ein Array mit einer Länge N und eine Summe S
• Erstellen Sie drei verschachtelte Schleifen. Die erste Schleife läuft von Anfang bis Ende (Schleifenzähler i), die zweite Schleife läuft ab i+1 bis zum Ende (Schleifenzähler j) und die dritte Schleife läuft ab j+1 bis zum Ende (Schleifenzähler k)
• Der Zähler dieser Schleifen stellt den Index von dar 3 Elemente der Triolen.
• Finden Sie die Summe des i-ten, j-ten und k-ten Elements. Wenn die Summe gleich der angegebenen Summe ist. Drucken Sie das Triplett aus und brechen Sie es.
• Wenn kein Triplett vorhanden ist, geben Sie aus, dass kein Triplett vorhanden ist.

Nachfolgend finden Sie die Umsetzung des oben genannten Ansatzes:

C++

Thread-Synchronisation

>

>

C

>

>

Java

>

>

Python3

>

>

C#

c-String im Array

>

>

Javascript

>

>

PHP

>

>

Triplet is 4, 10, 8>

Komplexitätsanalyse:

• Zeitkomplexität: An³), Es gibt drei verschachtelte Schleifen, die das Array durchlaufen, sodass die zeitliche Komplexität O(n^3) beträgt.
• Hilfsraum: O(1), da kein zusätzlicher Platz erforderlich ist.

Triplettsumme im Array (3sum) verwenden Zwei-Zeiger-Technik :

Durch Sortieren des Arrays kann die Effizienz des Algorithmus verbessert werden. Dieser effiziente Ansatz nutzt die Zwei-Zeiger-Technik . Durchlaufen Sie das Array und fixieren Sie das erste Element des Tripletts. Verwenden Sie nun den Zwei-Zeiger-Algorithmus, um herauszufinden, ob es ein Paar gibt, dessen Summe gleich ist x – Array[i] . Der Zwei-Zeiger-Algorithmus benötigt lineare Zeit und ist daher besser als eine verschachtelte Schleife.

Schritt-für-Schritt-Ansatz:

• Sortieren Sie das angegebene Array.
• Durchlaufen Sie das Array und fixieren Sie das erste Element des möglichen Tripletts. arr[i] .
• Dann fixieren Sie zwei Zeiger, einen bei ich + 1 und der andere bei n – 1 . Und schau dir die Summe an,
  • Wenn die Summe kleiner als die erforderliche Summe ist, erhöhen Sie den ersten Zeiger.
  • Andernfalls, wenn die Summe größer ist, verringern Sie den Endzeiger, um die Summe zu verringern.
  • Andernfalls, wenn die Summe der Elemente am Zwei-Zeiger gleich der angegebenen Summe ist, wird das Triplett gedruckt und unterbrochen.

Nachfolgend finden Sie die Umsetzung des oben genannten Ansatzes:

C++

>

>

C

>

>

Java

>

>

Python3

>

>

C#

Katrina Kaif

> 
    
   
 
     
  
 
    
Heap und Heap-Sortierung
 
     
     
    
 
 
 
 
 
 > // 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]>Summe r--;  } } // Wenn wir hier ankommen, wurde kein Triplett gefunden. return false; } /* Treiberprogramm zum Testen der obigen Funktion */ let A = [ 1, 4, 45, 6, 10, 8 ];  sei Summe = 22;  let arr_size = A.length;  find3Numbers(A, arr_size, sum); // Dieser Code wurde von Mayank Tyagi beigesteuert>
 
 
 
 
    
 
>
 
    
 
>
 
 
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]>Summe $r--;  } } // Wenn wir hier ankommen, dann // wurde kein Triplett gefunden return false; } // Treibercode $A = array (1, 4, 45, 6, 10, 8); $summe = 22; $arr_size = sizeof($A); find3Numbers($A, $arr_size, $sum); // Dieser Code wurde von ajit beigesteuert ?>>
 
 
 
 
    
 
>
 
    
 
>
 
  Ausgabe  
 
Triplet is 4, 8, 10>
 
    Komplexitätsanalyse:     
 
 
    Zeitkomplexität:    O(N^2). Es gibt nur zwei verschachtelte Schleifen, die das Array durchlaufen, daher ist die Zeitkomplexität O(n^2). Der Zwei-Zeiger-Algorithmus benötigt O(n) Zeit und das erste Element kann mithilfe einer weiteren verschachtelten Durchquerung behoben werden.
 
    Hilfsraum:    O(1), da kein zusätzlicher Platz erforderlich ist.
 
 
    Triplettsumme im Array (3sum)    verwenden  Hashing  :
  
 
Dieser Ansatz benötigt zusätzlichen Platz, ist jedoch einfacher als der Zwei-Zeiger-Ansatz. Führen Sie zwei Schleifen aus, die äußere Schleife vom Anfang bis zum Ende und die innere Schleife von Anfang bis Ende    i+1    beenden. Erstellen Sie eine Hashmap oder legen Sie fest, dass die Elemente dazwischen gespeichert werden    i+1    Zu    n-1    . Also, wenn die angegebene Summe ist    X,    Überprüfen Sie, ob es in der Menge eine Zahl gibt, die gleich ist    X         – arr[i] – arr[j]    . Wenn ja, drucken Sie das Triplett aus.
 
 
Schritt-für-Schritt-Ansatz:
 
 
Durchlaufen Sie das Array und korrigieren Sie das erste Element (    A[i]    ) für das Triplett.
 
Für jede    A[i]    , verwenden Sie eine Hashmap         um potenzielle zweite Elemente zu speichern, die die gewünschte Summe vervollständigen    (Summe – A[i])    .
 
Überprüfen Sie innerhalb einer verschachtelten Schleife, ob der Unterschied zwischen dem aktuellen Element (    A[j]    ) und die gewünschte Summe (    Summe – A[i]    ) ist in der Hashmap vorhanden. Wenn ja, wird ein Triplett gefunden, dann drucken Sie es aus.
 
Wenn im gesamten Array kein Triplett gefunden wird, kehrt die Funktion zurück    FALSCH    .
 
 
Nachfolgend finden Sie die Umsetzung des oben genannten Ansatzes:
 
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;  // Berechnen Sie die aktuelle Summe, die zum Erreichen der // Zielsumme erforderlich ist int curr_sum = sum - A[i];  // Iteriere durch das Subarray A[i+1..n-1], um // ein Paar mit der erforderlichen Summe für (int j = i + 1; j // zu finden. Berechne den erforderlichen Wert für das zweite // Element int require_value = curr_sum - A[j]; // Überprüfen Sie, ob der erforderliche Wert in der // Menge vorhanden ist if (s.find(required_value) != s.end()) { // Triplett wird gefunden; / elements printf('Triplet is %d, %d, %d', A[i], A[j], require_value); // Füge das aktuelle Element zur Menge für zukünftiges // Komplement hinzu checks s.insert(A[j]); 4, 45, 6, 10, 8 }; int sum = 22; int arr_size = sizeof(A) / sizeof(A[0]); // Rufen Sie die Funktion find3Numbers auf, um das Triplett zu finden und auszugeben, falls es existiert find3Numbers(A, arr_size, sum); return 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.'>)> 
 
 
 
 
    
Mathe-Zufalls-Java
 
>
 
    
 
>
 
 
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 = neues HashSet ();  // Berechnen Sie die aktuelle Summe, die zum Erreichen der // Zielsumme erforderlich ist int curr_sum = sum - arr[i];  // Iteriere das Subarray arr[i+1:] for (int j = i + 1; j // Berechne den erforderlichen Wert für das // zweite Element int require_value = curr_sum - arr[j]; // Überprüfen Sie, ob erforderlicher Wert ist im // HashSet vorhanden if (s.Contains(required_value)) { // Triplett wird gefunden; drucke das Triplett // Elemente Console.WriteLine('Triplet ist ' + arr[i] + ', ' + arr[j] + ', ' + require_value); return true } // Das aktuelle Element zum HashSet hinzufügen // für zukünftige Komplementprüfungen s.Add(arr[j]); Wenn kein Triplett gefunden wird, return false; // Treiberprogramm zum Testen der Find3Numbers-Funktion static void Main() { int[] arr = { 1, 4, 45, 6, 10, 8 }; ; // Rufen Sie die Funktion „Find3Numbers“ auf, um // das Triplett zu finden und auszugeben, falls es vorhanden ist if (!Find3Numbers(arr, target_sum)) { Console.WriteLine('Kein Triplett gefunden.');
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 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();>
 
 
 
 
    
 
>
 
    
 
>
 
  Ausgabe  
 
Triplet is 4, 8, 10>
 
    Zeitkomplexität:    O(N^2)  
    Hilfsraum:    O(N), da n zusätzlicher Platz belegt wurde
 
Die Erklärung des Problems können Sie sich hier ansehen  Youtube  besprochen vom Geeks For Geeks Team.
 
Sie können auch verweisen  Das  Video auf Youtube vorhanden.  
    Wie drucke ich alle Drillinge mit der angegebenen Summe aus?       
Verweisen Finden Sie alle Drillinge mit Nullsumme .