Dată o matrice arr[] de mărime n și un număr întreg X . Aflați dacă există un triplet în matrice care se însumează la întregul dat X .

salvare video youtube vlc

Exemple:

Intrare: matrice = {12, 3, 4, 1, 6, 9}, suma = 24;
Ieșire: 12, 3, 9
Explicaţie: Există un triplet (12, 3 și 9) prezent
în tabloul a cărui sumă este 24.

Intrare: matrice = {1, 2, 3, 4, 5}, suma = 9
Ieșire: 5, 3, 1
Explicaţie: Există un triplet (5, 3 și 1) prezent
în tabloul a cărui sumă este 9.

Sumă tripletă în matrice (sumă 3) prin generarea tuturor tripleților:

O metodă simplă este de a genera toate tripletele posibile și de a compara suma fiecărui triplet cu valoarea dată. Următorul cod implementează această metodă simplă folosind trei bucle imbricate.

Abordare pas cu pas:

• Dată o matrice de lungime n si o suma s
• Creați trei bucle imbricate prima buclă de la început până la sfârșit (contorul de bucle i), a doua buclă de la care se execută i+1 până la sfârșit (contorul de bucle j) și a treia buclă merge de la j+1 a se termina (contorul buclei k)
• Contorul acestor bucle reprezintă indicele de 3 elemente ale tripleților.
• Aflați suma al-lea, j-lea și k-lea element. Dacă suma este egală cu suma dată. Imprimați tripletul și rupeți.
• Dacă nu există triplet, imprimați că nu există triplet.

Mai jos este implementarea abordării de mai sus:

C++

>

>

C

>

>

Java

>

>

Python3

>

>

C#

>

>

Javascript

cum se deschide un fișier json

>

>

PHP

> 
    
 Triplet is 4, 10, 8>

Analiza complexității:

• Complexitatea timpului: Pe³), Există trei bucle imbricate care traversează matricea, deci complexitatea timpului este O(n^3)
• Spațiu auxiliar: O(1), deoarece nu este necesar spațiu suplimentar.

Sumă tripletă în matrice (sumă 3) folosind Tehnica cu două puncte :

Prin sortarea matricei, eficiența algoritmului poate fi îmbunătățită. Această abordare eficientă folosește tehnica cu două puncte . Traversați matricea și fixați primul element al tripletului. Acum utilizați algoritmul Two Pointers pentru a afla dacă există o pereche a cărei sumă este egală cu x – matrice[i] . Algoritmul cu doi pointeri ia timp liniar, deci este mai bun decât o buclă imbricată.

Abordare pas cu pas:

• Sortați matricea dată.
• Buclă peste matrice și fixează primul element al tripletului posibil, arr[i] .
• Apoi fixați două indicatoare, unul la i + 1 iar celălalt la n – 1 . Și uită-te la suma,
  • Dacă suma este mai mică decât suma necesară, creșteți primul indicator.
  • În caz contrar, dacă suma este mai mare, micșorați indicatorul final pentru a reduce suma.
  • În caz contrar, dacă suma elementelor de la două puncte este egală cu suma dată, imprimați tripletul și rupeți.

Mai jos este implementarea abordării de mai sus:

C++

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // C program to find a triplet> #include> #include> #include> int> cmpfunc(>const> void>* a,>const> void>* b)> {> >return> (*(>int>*)a - *(>int>*)b);> }> // 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 */> >qsort>(A, arr_size,>sizeof>(>int>), cmpfunc);> > >/* 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) {  printf('Triplet is %d, %d, %d', A[i], A[l],  A[r]);  return true;  }  else if (A[i] + A[l] + A[r]   l++;  else // A[i] + A[l] + A[r]>suma r--;  } } // Dacă ajungem aici, atunci nu a fost găsit niciun triplet return false; } /* Program driver pentru a testa funcția de mai sus */ int main() { int A[] = { 1, 4, 45, 6, 10, 8 };  int suma = 22;  int arr_size = dimensiunea(A) / dimensiunea(A[0]);  find3Numbers(A, arr_size, sum);  întoarce 0; } // Acest cod este contribuit de Aditya Kumar (adityakumar129)>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // Java program to find a triplet> class> FindTriplet {> >// returns true if there is triplet with sum equal> >// to 'sum' present in A[]. Also, prints the triplet> >boolean> 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 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  r = arr_size - 1; // index of the last element  while (l   if (A[i] + A[l] + A[r] == sum) {  System.out.print('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]>suma r--;  } } // Dacă ajungem aici, atunci nu a fost găsit niciun triplet return false;  } int partition(int A[], int si, int ei) { int x = A[ei];  int i = (si - 1);  int j;  pentru (j = si; j<= ei - 1; j++) {  if (A[j] <= x) {  i++;  int temp = A[i];  A[i] = A[j];  A[j] = temp;  }  }  int temp = A[i + 1];  A[i + 1] = A[ei];  A[ei] = temp;  return (i + 1);  }  /* Implementation of Quick Sort  A[] -->Array de sortat si --> Starting index ei --> Ending index */ void quickSort(int A[], int si, int ei) { int pi;  /* Index de partitionare */ if (si pi = partition(A, si, ei); quickSort(A, si, pi - 1); quickSort(A, pi + 1, ei); } } // Program driver de testat funcțiile de mai sus public static void main(String[] args) { FindTriplet triplet = new FindTriplet(] = { 1, 4, 45, 6, 10, 8 }; int sum = 22; lungime; triplet.find3Numbers(A, arr_size, sum);
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # 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 # Dacă ajungem aici, atunci # nu s-a găsit niciun triplet return False # Programul driver pentru a testa funcția de mai sus A = [1, 4, 45, 6, 10, 8] sum = 22 arr_size = len(A) find3Numbers(A, arr_size, sum) # Acesta este contribuit de Smitha Dinesh Semwal>>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // 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]>suma r--;  } } // Dacă ajungem aici, atunci // nu a fost găsit niciun triplet return false;  } int partition(int[] A, int si, int ei) { int x = A[ei];  int i = (si - 1);  int j;  pentru (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[] -->Matrice de sortat si --> Index de pornire ei --> Index final */ void quickSort(int[] A, int si, int ei) { int pi;  /* Index de partiție */ if (si pi = partition(A, si, ei); quickSort(A, si, pi - 1); quickSort(A, pi + 1, ei); } } // Cod driver static void Main() { GFG triplet = new GFG(); (A, arr_size, sum } } // Acest cod este contribuit de mits>'>).
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
jsp
 
     
     
    
 
 
 
 
 
 > // 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]>suma r--;  } } // Dacă ajungem aici, atunci nu a fost găsit niciun triplet return false; } /* Programul driver pentru a testa funcția de mai sus */ lasă A = [ 1, 4, 45, 6, 10, 8 ];  fie suma = 22;  fie arr_size = A.lungime;  find3Numbers(A, arr_size, sum); // Acest cod este contribuit de Mayank Tyagi>>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
  // 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--;  } } // Dacă ajungem aici, atunci // nu a fost găsit niciun triplet return false; } // Cod driver $A = matrice (1, 4, 45, 6, 10, 8); $sum = 22; $arr_size = dimensiunea($A); find3Numbers($A, $arr_size, $sum); // Acest cod este contribuit de ajit ?>>
 
 
 
 
    
 
>
 
    
 
>
 
  Ieșire  
 
Triplet is 4, 8, 10>
 
    Analiza complexității:     
 
 
    Complexitatea timpului:    O(N^2), Există doar două bucle imbricate care traversează matricea, deci complexitatea timpului este O(n^2). Algoritmul cu doi pointeri ia timp O(n), iar primul element poate fi fixat folosind o altă traversare imbricată.
 
    Spațiu auxiliar:    O(1), deoarece nu este necesar spațiu suplimentar.
 
 
    Sumă tripletă în matrice (sumă 3)    folosind  Hashing  :
  
 
Această abordare utilizează spațiu suplimentar, dar este mai simplă decât abordarea cu două puncte. Rulați două bucle bucla exterioară de la început până la sfârșit și bucla interioară de la    i+1    a se termina. Creați o hartă hash sau setați pentru a stoca elementele dintre acestea    i+1    la    n-1    . Deci, dacă suma dată este    X,    verificați dacă există un număr în set care este egal cu    X         – arr[i] – arr[j]    . Dacă da, tipăriți tripletul.
 
 
Abordare pas cu pas:
 
 
Iterați prin matrice, fixând primul element (    A[i]    ) pentru triplet.
 
Pentru fiecare    A[i]    , utilizați un Hashmap         pentru a stoca potențiale elemente secundare care completează suma dorită    (suma – A[i])    .
 
În interiorul unei bucle imbricate, verificați dacă diferența dintre elementul curent (    A[j]    ) și suma dorită (    suma – A[i]    ) este prezent în Hashmap. Dacă este, se găsește un triplet, apoi tipăriți-l.
 
Dacă nu se găsește niciun triplet în întregul tablou, funcția revine    fals    .
 
 
Mai jos este implementarea abordării de mai sus:
 
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;  // Calculați suma curentă necesară pentru a atinge // suma țintă int curr_sum = sum - A[i];  // Iterează prin subbarra A[i+1..n-1] pentru a găsi // o pereche cu suma necesară pentru (int j = i + 1; j // Calculați valoarea necesară pentru al doilea // element int required_value = curr_sum - A[j] // Verificați dacă valoarea necesară este prezentă în // set if (s.find(required_value) != s.end()) { // Se găsește tripletul //; / elemente printf('Tripletul este %d, %d, %d', A[i], A[j], returnează true } // Adăugați elementul curent pentru // complement; checks s.insert(A[j]); } } // Dacă nu se găsește niciun triplet, returnează false return false } /* Programul driver pentru a testa funcția */ int main() { int A[] = { 1, 4, 45, 6, 10, 8 }; int sum = 22 int arr_size = sizeof(A) / sizeof(A[0]); find3Numbers(A, arr_size, sum) returnează 0;
 
 
 
 
    
 
> 
    
   
 
     
  
înlocuiește-le pe toate
 
    
 
     
     
    
 
 
 
 
 
 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 = nou HashSet ();  // Calculați suma curentă necesară pentru a atinge // suma țintă int curr_sum = sum - arr[i];  // Iterează prin subbarra arr[i+1:] pentru (int j = i + 1; j // Calculați valoarea necesară pentru // al doilea element int required_value = curr_sum - arr[j]; // Verificați dacă valoarea necesară este prezentă în // HashSet if (s.Contains(required_value)) { // este găsit triplet // elementele Console.WriteLine('Triplet este ' + arr[i] + ', ' + arr[j] + ', ' + required_value return true } // Adăugați elementul curent la HashSet // pentru verificări complementare s.Add(arr[j]); Dacă nu se găsește niciun triplet, returnează false return false } // Programul driver pentru a testa funcția Find3Numbers static void Main() { int[] arr = { 1, 4, 45, 6, 10, 8 }; ; // Apelați funcția Find3Numbers pentru a găsi și tipări // tripletul, dacă acesta există dacă (!Find3Numbers(arr, target_sum)) { Console.WriteLine('Nu s-a găsit 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();>
 
 
 
 
    
 
>
 
    
 
>
 
  Ieșire  
 
Triplet is 4, 8, 10>
 
    Complexitatea timpului:    O(N^2)  
    Spațiu auxiliar:    O(N), deoarece a fost ocupat n spațiu suplimentar
 
Puteți urmări explicația problemei pe  YouTube  discutat de Geeks For Geeks Team.
 
De asemenea, vă puteți referi  acest  videoclip prezent pe Youtube.  
    Cum să tipăriți toate tripletele cu suma dată?       
Consultați Găsiți toate tripletele cu sumă zero .