Dada una matriz llegar[] de tamaño norte y un numero entero X . Encuentre si hay un triplete en la matriz que suma el número entero dado X .

Ejemplos:

Aporte: matriz = {12, 3, 4, 1, 6, 9}, suma = 24;
Producción: 12, 3, 9
Explicación: Hay un triplete (12, 3 y 9) presente.
en la matriz cuya suma es 24.

Aporte: matriz = {1, 2, 3, 4, 5}, suma = 9
Producción: 5, 3, 1
Explicación: Hay un triplete (5, 3 y 1) presente.
en la matriz cuya suma es 9.

Suma triplete en matriz (3sum) generando todos los tripletes:

Un método simple es generar todos los tripletes posibles y comparar la suma de cada triplete con el valor dado. El siguiente código implementa este método simple utilizando tres bucles anidados.

Enfoque paso a paso:

• Dada una matriz de longitud norte y una suma s
• Cree tres bucles anidados: el primer bucle se ejecuta de principio a fin (contador de bucles i), el segundo bucle se ejecuta desde yo+1 hasta el final (contador de bucle j) y el tercer bucle se ejecuta desde j+1 hasta el final (contador de bucle k)
• El contador de estos bucles representa el índice de 3 elementos de los trillizos.
• Encuentre la suma del elemento i, j y k. Si la suma es igual a la suma dada. Imprime el triplete y rompe.
• Si no hay ningún triplete, imprima que no existe ningún triplete.

A continuación se muestra la implementación del enfoque anterior:

C++

>

>

C

>

>

Java

>

>

Python3

>

>

C#

>

>

JavaScript

>

>

PHP

>

>

Triplet is 4, 10, 8>

Análisis de complejidad:

• Complejidad del tiempo: En³), Hay tres bucles anidados que atraviesan la matriz, por lo que la complejidad del tiempo es O (n ^ 3)
• Espacio Auxiliar: O(1), ya que no se requiere espacio adicional.

Suma triplete en matriz (3sum) usando Técnica de dos punteros :

Al ordenar la matriz se puede mejorar la eficiencia del algoritmo. Este enfoque eficiente utiliza el técnica de dos punteros . Recorre la matriz y fija el primer elemento del triplete. Ahora use el algoritmo de dos punteros para encontrar si hay un par cuya suma es igual a x – matriz [yo] . El algoritmo de dos punteros requiere tiempo lineal, por lo que es mejor que un bucle anidado.

Enfoque paso a paso:

• Ordena la matriz dada.
• Recorra la matriz y arregle el primer elemento del posible triplete, llegar[yo] .
• Luego arregle dos punteros, uno en yo + 1 y el otro en norte – 1 . Y mira la suma,
  • Si la suma es menor que la suma requerida, incremente el primer puntero.
  • De lo contrario, si la suma es mayor, disminuya el puntero final para reducir la suma.
  • De lo contrario, si la suma de los elementos en dos punteros es igual a la suma dada, imprima el triplete y divida.

A continuación se muestra la implementación del enfoque anterior:

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] suma r -= 1 # Si llegamos aquí, entonces # no se encontró ningún triplete return False # Programa controlador para probar la función anterior A = [1, 4, 45, 6, 10, 8] suma = 22 arr_size = len(A) find3Numbers(A, arr_size, sum) # Esto es una contribución 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]>suma r--;  } } // Si llegamos aquí, entonces // no se encontró ningún triplete return false;  } int partición(int[] A, int si, int ei) { int x = A[ei];  int i = (si - 1);  intj;  para (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[] -->Matriz a ordenar si --> Índice inicial ei --> Índice final */ void quickSort(int[] A, int si, int ei) { int pi;  /* Índice de partición */ if (si pi = partición(A, si, ei); quickSort(A, si, pi - 1); quickSort(A, pi + 1, ei); } } // Código de controlador static void Principal() { GFG triplete = nuevo GFG(); int[] A = nuevo int[] { 1, 4, 45, 6, 10, 8 }; int suma = 22; (A, arr_size, sum); } } // Este código es aportado por 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]>suma r--;  } } // Si llegamos aquí, entonces no se encontró ningún triplete return false; } /* Programa controlador para probar la función anterior */ let A = [ 1, 4, 45, 6, 10, 8 ];  sea ​​suma = 22;  let arr_size = A.length;  find3Numbers(A, arr_size, suma); // Este código es una contribución de 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--;  } } // Si llegamos aquí, entonces // no se encontró ningún triplete return false; } // Código del controlador $A = matriz (1, 4, 45, 6, 10, 8); $suma = 22; $arr_size = tamaño de($A); find3Numbers($A, $arr_size, $suma); // Este código es aportado por ajit ?>>
 
 
 
 
    
 
>
 
    
 
>
 
  Producción  
 
Triplet is 4, 8, 10>
 
    Análisis de complejidad:     
 
 
    Complejidad del tiempo:    O (N ^ 2), solo hay dos bucles anidados que atraviesan la matriz, por lo que la complejidad del tiempo es O (n ^ 2). El algoritmo de dos punteros requiere un tiempo O(n) y el primer elemento se puede arreglar mediante otro recorrido anidado.
 
    Espacio Auxiliar:    O(1), ya que no se requiere espacio adicional.
 
 
    Suma triplete en matriz (3sum)    usando  hash  :
  
 
Este enfoque utiliza espacio adicional pero es más simple que el enfoque de dos punteros. Ejecute dos bucles, el bucle exterior de principio a fin y el bucle interior desde    yo+1    para terminar. Cree un mapa hash o configúrelo para almacenar los elementos intermedios    yo+1    a    n-1    . Entonces si la suma dada es    X,    Comprueba si hay un número en el conjunto que sea igual a    X         – arreglo[i] – arreglo[j]    . En caso afirmativo, imprima el triplete.
 
 
Enfoque paso a paso:
 
 
Iterar a través de la matriz, arreglando el primer elemento (    Ai]    ) para el triplete.
 
Para cada    Ai]    , utiliza un mapa Hash         para almacenar segundos elementos potenciales que completen la suma deseada    (suma – A[i])    .
 
Dentro de un bucle anidado, verifique si la diferencia entre el elemento actual (    A[j]    ) y la suma deseada (    suma – A[i]    ) está presente en el Hashmap. Si es así, se encuentra un triplete, imprímalo.
 
Si no se encuentra ningún triplete en toda la matriz, la función devuelve    FALSO    .
 
 
A continuación se muestra la implementación del enfoque anterior:
 
C++
    
 
     
  
 
    
iterar mapa en java
 
     
     
    
 
 
 
 
 
 #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;  // Calcular la suma actual necesaria para alcanzar la // suma objetivo int curr_sum = sum - A[i];  // Iterar a través del subarreglo A[i+1..n-1] para encontrar // un par con la suma requerida para (int j = i + 1; j // Calcular el valor requerido para el segundo // elemento int valor_requerido = suma_curr - A[j] // Comprobar si el valor requerido está presente en // establecer if (s.find(valor_requerido) != s.end()) { // Se encuentra el triplete / / elementos printf('Triplet es %d, %d, %d', A[i], A[j], valor_requerido return true } // Agrega el elemento actual al conjunto para // complemento futuro); checks s.insert(A[j]); } } // Si no se encuentra ningún triplete, devuelve false return false } /* Programa controlador para probar la función anterior */ int main() { int A[] = { 1, 4, 45, 6, 10, 8 }; int sum = 22; int arr_size = sizeof(A) / sizeof(A[0]); // Llama a la función find3Numbers para buscar e imprimir el // triplete, si existe. find3Numbers(A, arr_size, suma); devuelve 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.');  }  } }>
 
 
 
 
    
 
>
 
    
 
>
 
 
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 = nuevo HashSet ();  // Calcular la suma actual necesaria para alcanzar la // suma objetivo int curr_sum = sum - arr[i];  // Iterar a través del subarreglo arr[i+1:] for (int j = i + 1; j // Calcular el valor requerido para el // segundo elemento int require_value = curr_sum - arr[j]; // Comprobar si el el valor requerido está presente en // el HashSet if (s.Contains(required_value)) { // Se encuentra el triplete; imprime el triplete // elementos Console.WriteLine('Triplet is ' + arr[i] + ', ' + arr[j] + ', ' + require_value); return true; // Agrega el elemento actual al HashSet // para futuras comprobaciones de complemento s.Add(arr[j]); Si no se encuentra ningún triplete, devuelve false return false } // Programa controlador para probar la función Find3Numbers static void Main() { int[] arr = { 1, 4, 45, 6, 10, 8 }; ; // Llame a la función Find3Numbers para buscar e imprimir // el triplete, si existe if (!Find3Numbers(arr, target_sum)) { Console.WriteLine('No se encontró ningún triplete.');
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 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();>
 
 
 
 
    
 
>
 
    
 
>
 
  Producción  
 
Triplet is 4, 8, 10>
 
    Complejidad del tiempo:    O(N^2)  
    Espacio Auxiliar:    O(N), ya que se ha tomado n espacio adicional
 
Puedes ver la explicación del problema en  YouTube  discutido por el equipo de Geeks For Geeks.
 
También puedes referirte  este  vídeo presente en Youtube.  
    ¿Cómo imprimir todos los tripletes con una suma determinada?       
Referirse Encuentra todos los tripletes con suma cero .