Dané pole arr[] veľkosti n a celé číslo X . Zistite, či je v poli trojica, ktorej súčet tvorí dané celé číslo X .

Príklady:

Vstup: pole = {12, 3, 4, 1, 6, 9}, súčet = 24;
Výkon: 12, 3, 9
Vysvetlenie: Prítomná je trojica (12, 3 a 9).
v poli, ktorého súčet je 24.

Vstup: pole = {1, 2, 3, 4, 5}, súčet = 9
Výkon: 5, 3, 1
Vysvetlenie: Prítomná je trojica (5, 3 a 1).
v poli, ktorého súčet je 9.

Trojitý súčet v poli (3 súčet) vygenerovaním všetkých trojíc:

Jednoduchým spôsobom je vygenerovať všetky možné triplety a porovnať súčet každého tripletu s danou hodnotou. Nasledujúci kód implementuje túto jednoduchú metódu pomocou troch vnorených slučiek.

Postupný prístup:

• Vzhľadom na pole dĺžky n a sumu s
• Vytvorte tri vnorené slučky, prvá slučka prebieha od začiatku do konca (počítadlo slučky i), druhá slučka prebieha od i+1 do konca (počítadlo slučky j) a tretia slučka prebieha od j+1 skončiť (počítadlo k)
• Počítadlo týchto slučiek predstavuje index 3 prvky trojíc.
• Nájdite súčet i-tého, j-tého a k-tého prvku. Ak sa súčet rovná danej sume. Vytlačte trojicu a zlomte.
• Ak neexistuje žiadna trojica, vypíšte, že žiadna trojica neexistuje.

Nižšie je uvedená implementácia vyššie uvedeného prístupu:

C++

>

>

C

>

>

Java

>

>

Python3

>

java typeof premennej

>

C#

>

>

Javascript

>

>

PHP

>

>

Triplet is 4, 10, 8>

Analýza zložitosti:

• Časová zložitosť: O(n³), Pole prechádzajú tri vnorené slučky, takže časová zložitosť je O(n^3)
• Pomocný priestor: O(1), pretože nie je potrebný žiadny ďalší priestor.

Trojitý súčet v poli (3 súčet) použitím Technika dvoch ukazovateľov :

Triedením poľa je možné zlepšiť účinnosť algoritmu. Tento efektívny prístup využíva dvojbodová technika . Prejdite po poli a opravte prvý prvok trojice. Teraz použite algoritmus dvoch ukazovateľov na zistenie, či existuje pár, ktorého súčet sa rovná x – pole[i] . Algoritmus dvoch ukazovateľov trvá lineárny čas, takže je lepší ako vnorená slučka.

Postupný prístup:

• Zoradiť dané pole.
• Opakujte pole a opravte prvý prvok možnej trojice, arr[i] .
• Potom opravte dva ukazovatele, jeden na i + 1 a druhý pri n – 1 . A pozrite sa na sumu,
  • Ak je súčet menší ako požadovaný súčet, zvýšte prvý ukazovateľ.
  • Inak, ak je súčet väčší, Znížte koncový ukazovateľ, aby ste znížili súčet.
  • V opačnom prípade, ak sa súčet prvkov v dvojbodke rovná danému súčtu, vytlačte trojicu a zlomte.

Nižšie je uvedená implementácia vyššie uvedeného prístupu:

C++

>

>

C

>

>

Java

prvý notebook

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # 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] súčet r -= 1 # Ak sa dostaneme sem, potom # sa nenašla žiadna trojica return False # Program ovládača na testovanie funkcie A = [1, 4, 45, 6, 10, 8] súčet = 22 arr_size = len(A) find3Numbers(A, arr_size, sum) # Prispel 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]>súčet r--;  } } // Ak sa dostaneme sem, potom // nebola nájdená žiadna trojica return false;  } int partition(int[] A, int si, int ei) { int x = A[ei];  int i = (si - 1);  int j;  pre (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[] -->Pole na triedenie si --> Počiatočný index ei --> Koncový index */ void quickSort(int[] A, int si, int ei) { int pi;  /* Index rozdelenia */ if (si pi = partition(A, si, ei); quickSort(A, si, pi - 1); quickSort(A, pi + 1, ei); } } // Kód ovládača staticky void Main() { GFG triplet = new GFG(] A = new int[] { 1, 4, 45, 6, 10, 8 }; int arr_velkost = A.Dlzka (A, arr_size, sum, } } // Tento kód prispel 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]>súčet r--;  } } // Ak sa dostaneme sem, nenašla sa žiadna trojica return false; } /* Program ovládača na testovanie vyššie uvedenej funkcie */ nech A = [ 1, 4, 45, 6, 10, 8 ];  nech súčet = 22;  nech arr_size = A.length;  nájdi3čísla(A, veľkosť_arr, súčet); // Tento kód prispel 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]>suma $r--;  } } // Ak sa dostaneme sem, potom // nebola nájdená žiadna trojica return false; } // Kód ovládača $A = pole (1, 4, 45, 6, 10, 8); $sum = 22; $arr_size = sizeof($A); find3Numbers($A, $veľkosť_pola, $suma); // Do tohto kódu prispel ajit ?>>
 
 
 
 
    
 
>
 
onclick javascript
    
 
>
 
  Výkon  
 
Triplet is 4, 8, 10>
 
    Analýza zložitosti:     
 
 
    Časová zložitosť:    O(N^2), Pole prechádzajú iba dve vnorené slučky, takže časová zložitosť je O(n^2). Algoritmus dvoch ukazovateľov trvá O(n) čas a prvý prvok možno opraviť pomocou iného vnoreného prechodu.
 
    Pomocný priestor:    O(1), pretože nie je potrebný žiadny ďalší priestor.
 
 
    Trojitý súčet v poli (3 súčet)    použitím  Hašovanie  :
  
 
Tento prístup využíva priestor navyše, ale je jednoduchší ako prístup dvoch ukazovateľov. Spustite dve slučky vonkajšiu slučku od začiatku do konca a vnútornú slučku od    i+1    do konca. Vytvorte hashmapu alebo sadu na uloženie prvkov medzi nimi    i+1    do    n-1    . Ak teda daná suma je    X,    skontrolujte, či je v množine číslo, ktoré sa rovná    X         – arr[i] – arr[j]    . Ak áno, vytlačte trojicu.
 
 
Postupný prístup:
 
 
Iterujte cez pole a opravte prvý prvok (    A[i]    ) pre trojku.
 
Pre každý    A[i]    , použite Hashmap         uložiť potenciálne druhé prvky, ktoré dokončia požadovaný súčet    (súčet – A[i])    .
 
Vo vnútri vnorenej slučky skontrolujte, či je rozdiel medzi aktuálnym prvkom (    A[j]    ) a požadovanú sumu (    súčet – A[i]    ) sa nachádza v Hashmape. Ak áno, nájde sa trojica, potom ju vytlačte.
 
Ak sa v celom poli nenájde žiadna trojica, funkcia sa vráti    falošný    .
 
 
Nižšie je uvedená implementácia vyššie uvedeného prístupu:
 
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;  // Vypočítajte aktuálnu sumu potrebnú na dosiahnutie // cieľovej sumy int curr_sum = suma - A[i];  // Iterujte cez podpole A[i+1..n-1] a nájdite // pár s požadovaným súčtom pre (int j = i + 1; j // Vypočítajte požadovanú hodnotu pre druhý // prvok int požadovaná_hodnota = curr_sum - A[j] // Skontrolujte, či je požadovaná hodnota prítomná v množine // if (s.find(požadovaná_hodnota) != s.end()) { // Triplet sa našiel /; / prvky printf('Trojica je %d, %d, %d', A[i], A[j], požadovaná_hodnota návrat true } // Pridanie aktuálneho prvku do množiny pre budúci // doplnok; checks s.insert(A[j] } } // Ak sa nenájde žiadny triplet, vráti false return false } /* Program ovládača na testovanie funkcie */ int main() { int A[] = { 1, 4, 45, 6, 10, 8 }; int sum = 22; int arr_size = sizeof(A) / sizeof(A[0] // Zavolajte funkciu find3Numbers na nájdenie a vytlačenie // tripletu, ak existuje nájdi3čísla(A, veľkosť_pola, súčet }>
 
 
 
 
    
 
>
 
    
 
>
 
 
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.'>)> 
 
 
 
 
    
pole reťazcov v programovaní v c
 
>
 
    
 
>
 
 
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 = nový HashSet ();  // Vypočítajte aktuálnu sumu potrebnú na dosiahnutie // cieľovej sumy int curr_sum = sum - arr[i];  // Iterácia cez podpole arr[i+1:] for (int j = i + 1; j // Vypočítajte požadovanú hodnotu pre // druhý prvok int required_value = curr_sum - arr[j]; // Skontrolujte, či požadovaná hodnota je prítomná v // HashSet if (s.Contains(required_value)) { // Triplet sa našiel // vypíše prvky Console.WriteLine('Triplet je ' + arr[i] + ', ' + arr[j] + ', ' + požadovaná_hodnota return true } // Pridajte aktuálny prvok do HashSet // pre budúce kontroly doplnkov s.Add(arr[j]); Ak sa nenájde žiadny triplet, vráti false return false } // Program ovládača na testovanie funkcie Find3Numbers static void Main() { int[] arr = { 1, 4, 45, 6, 10, 8 }; ; // Zavolajte funkciu Find3Numbers na nájdenie a vytlačenie // tripletu, ak existuje if (!Find3Numbers(arr, target_sum)) { Console.WriteLine('Nenašiel sa žiadny triplet.');
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 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();>
 
 
 
 
    
 
>
 
    
 
>
 
  Výkon  
 
Triplet is 4, 8, 10>
 
    Časová zložitosť:    O(N^2)  
    Pomocný priestor:    O(N), keďže bolo zabratých n miesta navyše
 
Vysvetlenie problému si môžete pozrieť na  YouTube  diskutované tímom Geeks For Geeks.
 
Môžete tiež odkazovať  toto  video prezentované na Youtube.  
    Ako vytlačiť všetky trojičky s daným súčtom?       
Odkazovať Nájdite všetky trojice s nulovým súčtom .