Donada una matriu arr[] de mida n i un nombre enter X . Cerqueu si hi ha un triplet a la matriu que suma l'enter donat X .

Exemples:

Entrada: matriu = {12, 3, 4, 1, 6, 9}, suma = 24;
Sortida: 12, 3, 9
Explicació: Hi ha un triplet (12, 3 i 9) present
a la matriu la suma de la qual és 24.

Entrada: matriu = {1, 2, 3, 4, 5}, suma = 9
Sortida: 5, 3, 1
Explicació: Hi ha un triplet (5, 3 i 1) present
a la matriu la suma de la qual és 9.

Suma triplet en matriu (3sum) generant tots els triplets:

Un mètode senzill és generar tots els triplets possibles i comparar la suma de cada triplet amb el valor donat. El codi següent implementa aquest mètode senzill mitjançant tres bucles imbricats.

Enfocament pas a pas:

• Donada una matriu de longitud n i una suma s
• Creeu tres cicles de primer bucle imbricats des de l'inici fins al final (comptador de bucles i), des del segon bucle i+1 fins al final (comptador de bucles j) i el tercer bucle va des de j+1 per acabar (comptador de bucles k)
• El comptador d'aquests bucles representa l'índex de 3 elements dels tres bessons.
• Trobeu la suma dels elements iè, jè i kè. Si la suma és igual a la suma donada. Imprimeix el triplet i trenca.
• Si no hi ha triplet, imprimiu que no existeix.

A continuació es mostra la implementació de l'enfocament anterior:

C++

>

>

C

>

>

Java

>

>

Python 3

>

>

C#

>

convertir nfa en dfa

>

Javascript

>

>

PHP

>

>

Triplet is 4, 10, 8>

Anàlisi de complexitat:

• Complexitat temporal: O (n³), Hi ha tres bucles imbricats que travessen la matriu, de manera que la complexitat del temps és O(n^3)
• Espai auxiliar: O(1), ja que no cal espai addicional.

Suma triplet en matriu (3sum) utilitzant Tècnica de dos punters :

En ordenar la matriu, es pot millorar l'eficiència de l'algorisme. Aquest enfocament eficient utilitza el tècnica de dos punters . Travessa la matriu i fixa el primer element del triplet. Ara utilitzeu l'algorisme de dos punters per trobar si hi ha un parell la suma del qual és igual x – matriu[i] . L'algorisme de dos punters triga un temps lineal, de manera que és millor que un bucle imbricat.

Enfocament pas a pas:

• Ordena la matriu donada.
• Feu un bucle sobre la matriu i fixeu el primer element del possible triplet, arr[i] .
• A continuació, fixeu dos punters, un a i + 1 i l'altre a n-1 . I mira la suma,
  • Si la suma és menor que la suma requerida, incrementeu el primer punter.
  • En cas contrari, si la suma és més gran, reduïu el punter final per reduir la suma.
  • En cas contrari, si la suma d'elements a dos punters és igual a la suma donada, llavors imprimeix el triplet i trenca.

A continuació es mostra la implementació de l'enfocament anterior:

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--;  } } // Si arribem aquí, no s'ha trobat cap triplet return false; } /* Programa de controlador per provar la funció anterior */ int main() { int A[] = { 1, 4, 45, 6, 10, 8 };  int suma = 22;  int arr_size = grandària de (A) / grandària de (A[0]);  find3Numbers(A, arr_size, suma);  retorn 0; } // Aquest codi és aportat per 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--;  } } // Si arribem aquí, no s'ha trobat cap triplet return false;  } int partició (int A[], int si, int ei) { int x = A[ei];  int i = (si - 1);  int j;  per (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[] -->Matriu a ordenar si --> Índex inicial ei --> Índex final */ void quickSort(int A[], int si, int ei) { int pi;  /* Índex de partició */ if (si pi = partició (A, si, ei); quickSort (A, si, pi - 1); quickSort (A, pi + 1, ei); } } // Programa de controlador per provar les funcions anteriors public static void main(String[] args) { FindTriplet triplet = new FindTriplet(] = { 1, 4, 45, 6, 10, 8 } int sum = 22; longitud; 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 # Si arribem aquí, aleshores # no s'ha trobat cap triplet retorn Fals # Programa del controlador per provar la funció anterior A = [1, 4, 45, 6, 10, 8] sum = 22 arr_size = len(A) find3Numbers(A, arr_size, sum) # Això és aportat per 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--;  } } // Si arribem aquí, aleshores // no s'ha trobat cap triplet return false;  } int partició (int[] A, int si, int ei) { int x = A[ei];  int i = (si - 1);  int j;  per (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[] -->Matriu a ordenar si --> Índex inicial ei --> Índex final */ void quickSort(int[] A, int si, int ei) { int pi;  /* Índex de partició */ if (si pi = partició (A, si, ei); quickSort (A, si, pi - 1); quickSort (A, pi + 1, ei); } } // Codi del controlador static void Main() { GFG triplet = new GFG(); (A, arr_size, sum } } // Aquest codi és aportat per mits>'>).
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 > // 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--;  } } // Si arribem aquí, no s'ha trobat cap triplet return false; } /* Programa de controlador per provar la funció anterior */ deixa A = [ 1, 4, 45, 6, 10, 8 ];  siguem suma = 22;  deixa arr_size = A.longitud;  find3Numbers(A, arr_size, suma); // Aquest codi és aportat per 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--;  } } // Si arribem aquí, aleshores // no s'ha trobat cap triplet return false; } // Codi del controlador $A = matriu (1, 4, 45, 6, 10, 8); $sum = 22; $arr_size = sizeof($A); find3Numbers($A, $arr_size, $sum); // Aquest codi és aportat per ajit ?>>
 
 
 
 
    
 
>
 
    
 
>
 
  Sortida  
 
Triplet is 4, 8, 10>
 
    Anàlisi de complexitat:     
 
 
    Complexitat temporal:    O(N^2), només hi ha dos bucles imbricats que travessen la matriu, de manera que la complexitat temporal és O(n^2). L'algorisme de dos punters pren temps O(n) i el primer element es pot arreglar mitjançant un altre recorregut imbricat.
 
    Espai auxiliar:    O(1), ja que no cal espai addicional.
 
 
    Suma triplet en matriu (3sum)    utilitzant  Hashing  :
  
 
Aquest enfocament utilitza espai addicional, però és més senzill que l'enfocament de dos punters. Executeu dos bucles exteriors des del principi fins al final i des de l'interior    i+1    per acabar. Creeu un hashmap o configureu per emmagatzemar els elements entremig    i+1    a    n-1    . Per tant, si la suma donada és    x,    comproveu si hi ha un nombre al conjunt que sigui igual a    x         – arr[i] – arr[j]    . En cas afirmatiu, imprimiu el triplet.
 
 
Enfocament pas a pas:
 
 
Itera per la matriu, fixant el primer element (    A[i]    ) per al triplet.
 
Per cadascú    A[i]    , utilitzeu un Hashmap         per emmagatzemar segons elements potencials que completen la suma desitjada    (suma – A[i])    .
 
Dins d'un bucle imbricat, comproveu si la diferència entre l'element actual (    A[j]    ) i la suma desitjada (    suma - A[i]    ) està present al Hashmap. Si és així, es troba un triplet i després imprimiu-lo.
 
Si no es troba cap triplet a tota la matriu, la funció torna    fals    .
 
 
A continuació es mostra la implementació de l'enfocament anterior:
 
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 la suma actual necessària per assolir // la suma objectiu int curr_sum = sum - A[i];  // Recorre el subbarray A[i+1..n-1] per trobar // un parell amb la suma necessària per a (int j = i + 1; j // Calcula el valor requerit per al segon // element int required_value = curr_sum - A[j] // Comprova si el valor requerit està present al // set if (s.find(required_value) != s.end()) { // es troba el triplet //; / elements printf('Triplet és %d, %d, %d', A[i], A[j], valor_necessari } // Afegeix l'element actual al conjunt per // complement); checks s.insert(A[j]); } } // Si no es troba cap triplet, retorna false return false } /* Controlador per provar la funció */ 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); retorna 0;
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 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.');  }  } }>
 
 
 
 
    
 
>
 
    
 
>
 
 
Python 3
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # 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 la suma actual necessària per assolir // la suma objectiu int curr_sum = sum - arr[i];  // Recorre el subbarray arr[i+1:] per a (int j = i + 1; j // Calcula el valor necessari per al // segon element int valor_necessari = curr_sum - arr[j]; // Comprova si el el valor requerit està present al // HashSet if (s.Contains(required_value)) { // es troba el triplet // imprimeix els elements Console.WriteLine('Triplet és ' + arr[i] + ', ' + arr[j] + ', ' + required_value } // Afegeix l'element actual al HashSet // per a futures comprovacions de complement } } //; Si no es troba cap triplet, retorna false return false } // Programa del controlador per provar la funció Find3Numbers static void Main() { int[] arr = { 1, 4, 45, 6, 10, 8 }; int target_sum = 22 ; // Crida a la funció Find3Numbers per trobar i imprimir // el triplet, si existeix si (!Find3Numbers(arr, target_sum)) { Console.WriteLine('No s'ha trobat un 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();>
 
 
 
 
    
 
>
 
    
 
>
 
  Sortida  
 
Triplet is 4, 8, 10>
 
    Complexitat temporal:    O(N^2)  
    Espai auxiliar:    O(N), ja que s'ha ocupat n espai addicional
 
Podeu veure l'explicació del problema a  YouTube  discutit per l'equip Geeks For Geeks.
 
També pots consultar  això  vídeo present a Youtube.  
    Com imprimir tots els triplets amb una suma determinada?       
Consulteu Troba tots els triplets amb suma zero .