Dada una serie de elementos distintos. La tarea es encontrar tripletes en una array cuya suma sea igual a un número dado.
Ejemplos:
Input: arr[] = {0, -1, 2, -3, 1}
sum = -2
Output: 0 -3 1
-1 2 -3
If we calculate the sum of the output,
0 + (-3) + 1 = -2
(-1) + 2 + (-3) = -2
Input: arr[] = {1, -2, 1, 0, 5}
sum = 0
Output: 1 -2 1
If we calculate the sum of the output,
1 + (-2) + 1 = 0
Método 1 : Fuerza bruta.
Enfoque: El enfoque de fuerza bruta en este tipo de preguntas tiene como objetivo verificar todos los tripletes posibles presentes en la array. El triplete con sum=Target sum será la respuesta. Ahora la pregunta que surge es cómo se deben verificar todos los tripletes posibles. Para verificar todas las duplas posibles, fije un puntero en un elemento y, para cada uno de esos elementos, recorra la array y verifique la suma. Esta será la suma de todas las duplas posibles .
Del mismo modo, para verificar todos los tripletes posibles , uno puede fijar dos punteros y mover el tercer puntero sobre la array y tan pronto como llegue al final de la array, incremente el segundo puntero y repita lo mismo.
Algoritmo:
- Tome tres punteros i , j , k .
- Inicialice i con cero e inicie un bucle anidado para i .
- Inicialice j con (i+1) e inicie un ciclo anidado para j .
- Inicialice k con (j+1) e inicie un bucle para k .
- Si Target == arr[i] + arr[j] + arr[k] rompe el bucle e imprime los valores de arr[i], arr[j], arr[k] .
- De lo contrario, siga incrementando k hasta que sea igual al último índice .
- Vaya al paso 2 e incremente j y para cada valor de j ejecute el ciclo interno de k .
- Si j es igual al 2º último índice Vaya al paso 1 e incremente el valor de i hasta el 3º último índice y nuevamente continúe todo el proceso hasta que el valor de i sea igual al último índice.
C++
// A simple C++ program to find three elements
// whose sum is equal to given sum
#include <bits/stdc++.h>
using namespace std;
// Prints all triplets in arr[] with given sum
void findTriplets(int arr[], int n, int sum)
{
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
if (arr[i] + arr[j] + arr[k] == sum) {
cout << arr[i] << " "
<< arr[j] << " "
<< arr[k] << endl;
}
}
}
}
}
// Driver code
int main()
{
int arr[] = { 0, -1, 2, -3, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
findTriplets(arr, n, -2);
return 0;
}
Java
// A simple Java program
// to find three elements
// whose sum is equal to
// given sum
import java.io.*;
class GFG {
// Prints all triplets in
// arr[] with given sum
static void findTriplets(int arr[],
int n, int sum)
{
for (int i = 0;
i < n - 2; i++) {
for (int j = i + 1;
j < n - 1; j++) {
for (int k = j + 1;
k < n; k++) {
if (arr[i] + arr[j] + arr[k] == sum) {
System.out.println(
arr[i] + " " + arr[j]
+ " " + arr[k]);
}
}
}
}
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 0, -1, 2, -3, 1 };
int n = arr.length;
findTriplets(arr, n, -2);
}
}
// This code is contributed by m_kit
Python3
# A simple Python 3 program # to find three elements # whose sum is equal to # given sum # Prints all triplets in # arr[] with given sum def findTriplets(arr, n, sum): for i in range(0, n - 2): for j in range(i + 1, n - 1): for k in range(j + 1, n): if (arr[i] + arr[j] + arr[k] == sum): print(arr[i], " ", arr[j], " ", arr[k], sep = "") # Driver code arr = [ 0, -1, 2, -3, 1 ] n = len(arr) findTriplets(arr, n, -2) # This code is contributed # by Smitha
C#
// A simple C# program
// to find three elements
// whose sum is equal to
// given sum
using System;
class GFG {
// Prints all triplets in
// arr[] with given sum
static void findTriplets(int[] arr,
int n, int sum)
{
for (int i = 0;
i < n - 2; i++) {
for (int j = i + 1;
j < n - 1; j++) {
for (int k = j + 1;
k < n; k++) {
if (arr[i] + arr[j] + arr[k] == sum) {
Console.WriteLine(
arr[i] + " " + arr[j]
+ " " + arr[k]);
}
}
}
}
}
// Driver code
static public void Main()
{
int[] arr = { 0, -1, 2, -3, 1 };
int n = arr.Length;
findTriplets(arr, n, -2);
}
}
// This code is contributed by akt_mit
PHP
<?php
// A simple PHP program to
// find three elements whose
// sum is equal to given sum
// Prints all triplets in
// arr[] with given sum
function findTriplets($arr, $n, $sum)
{
for ($i = 0; $i < $n - 2; $i++)
{
for ($j = $i + 1; $j < $n - 1; $j++)
{
for ($k = $j + 1; $k < $n; $k++)
{
if ($arr[$i] + $arr[$j] +
$arr[$k] == $sum)
{
echo $arr[$i], " ",
$arr[$j], " ",
$arr[$k], "\n";
}
}
}
}
}
// Driver code
$arr = array (0, -1, 2, -3, 1);
$n = sizeof($arr);
findTriplets($arr, $n, -2);
// This code is contributed by aj_36
?>
Javascript
<script>
// A simple Javascript program to find three elements
// whose sum is equal to given sum
// Prints all triplets in arr[] with given sum
function findTriplets(arr, n, sum)
{
for (let i = 0; i < n - 2; i++) {
for (let j = i + 1; j < n - 1; j++) {
for (let k = j + 1; k < n; k++) {
if (arr[i] + arr[j] + arr[k] == sum) {
document.write(arr[i]+ " "
+ arr[j] + " "
+ arr[k] + "<br>");
}
}
}
}
}
// Driver code
let arr = [ 0, -1, 2, -3, 1 ];
let n = arr.length;
findTriplets(arr, n, -2);
// This code is contributed by Mayank Tyagi
</script>
Producción :
0 -3 1 -1 2 -3
Análisis de Complejidad:
- Complejidad Temporal: O(n 3 ).
Se han utilizado tres bucles for anidados. - Espacio Auxiliar: O(1).
Como no se ha utilizado ninguna estructura de datos para almacenar valores.
Método 2 : hash.
Enfoque:
Se puede usar hash para resolver este problema. HashTable o HashMaps nos permite realizar operaciones de consulta o búsqueda en una complejidad de tiempo constante. Si uno puede encontrar que para cada doblete posible hay un elemento que ya existe en la array que puede hacer suma = suma objetivo, entonces el problema se resolverá de manera eficiente.
Para implementar Hashing, podemos usar unordered_set en C++ o HashSet en Java .
- A medida que arreglamos el primer puntero (digamos a) , atravesamos la array usando el segundo puntero (digamos b) y seguimos almacenando los elementos encontrados en una HashTable .
- Tan pronto como encontremos que el elemento que es igual a la suma restante (Target sum -(a+b)) que ya está presente en HashTable , imprimimos nuestro triplete.
Algoritmo:
- Inicie el bucle exterior desde i=0 hasta el índice (n-2) .
- Para cada iteración, haga un conjunto desordenado e ingrese el ciclo interno.
- Inicie el ciclo interno [desde j = (i+1) (ya que los valores con los que ya hemos verificado no aparecerán en un triplete válido) hasta el último índice.
- Compruebe si el elemento x = Target -(arr[i] + arr[j]) está presente, luego se encuentra el triplete y, por lo tanto, se imprime.
- De lo contrario, presione el valor en el conjunto como para una referencia posterior.
- Incremente i y vaya al paso 2.
Pseudocódigo:
Run a loop from i=0 to n-2
Create an empty hash table
Run inner loop from j=i+1 to n-1
If -(arr[i] + arr[j]) is present in hash table
print arr[i], arr[j] and -(arr[i] + arr[j])
Else
Insert arr[j] in hash table.
C++
// C++ program to find triplets in a given
// array whose sum is equal to given sum.
#include <bits/stdc++.h>
using namespace std;
// function to print triplets with given sum
void findTriplets(int arr[], int n, int sum)
{
for (int i = 0; i < n - 1; i++) {
// Find all pairs with sum equals to
// "sum-arr[i]"
unordered_set<int> s;
for (int j = i + 1; j < n; j++) {
int x = sum - (arr[i] + arr[j]);
if (s.find(x) != s.end())
printf("%d %d %d\n", x, arr[i], arr[j]);
else
s.insert(arr[j]);
}
}
}
// Driver code
int main()
{
int arr[] = { 0, -1, 2, -3, 1 };
int sum = -2;
int n = sizeof(arr) / sizeof(arr[0]);
findTriplets(arr, n, sum);
return 0;
}
Java
// Java program to find triplets in a given
// array whose sum is equal to given sum.
import java.util.*;
class GFG {
// function to print triplets with given sum
static void findTriplets(int arr[], int n, int sum)
{
for (int i = 0; i < n - 1; i++) {
// Find all pairs with sum equals to
// "sum-arr[i]"
HashSet<Integer> s = new HashSet<>();
for (int j = i + 1; j < n; j++) {
int x = sum - (arr[i] + arr[j]);
if (s.contains(x))
System.out.printf(
"%d %d %d\n", x, arr[i], arr[j]);
else
s.add(arr[j]);
}
}
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 0, -1, 2, -3, 1 };
int sum = -2;
int n = arr.length;
findTriplets(arr, n, sum);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to find triplets in a given # array whose Sum is equal to given sum. import math as mt # function to print triplets with given sum def findTriplets(arr, n, Sum): for i in range(n - 1): # Find all pairs with Sum equals # to "Sum-arr[i]" s = dict() for j in range(i + 1, n): x = Sum - (arr[i] + arr[j]) if x in s.keys(): print(x, arr[i], arr[j]) else: s[arr[j]] = 1 # Driver code arr = [ 0, -1, 2, -3, 1 ] Sum = -2 n = len(arr) findTriplets(arr, n, Sum) # This code is contributed # by mohit kumar 29
C#
// C# program to find triplets in a given
// array whose sum is equal to given sum.
using System;
using System.Collections.Generic;
public class GFG {
// function to print triplets with given sum
static void findTriplets(int[] arr, int n, int sum)
{
for (int i = 0; i < n - 1; i++) {
// Find all pairs with sum equals to
// "sum-arr[i]"
HashSet<int> s = new HashSet<int>();
for (int j = i + 1; j < n; j++) {
int x = sum - (arr[i] + arr[j]);
if (s.Contains(x))
Console.Write("{0} {1} {2}\n", x, arr[i], arr[j]);
else
s.Add(arr[j]);
}
}
}
// Driver code
public static void Main(String[] args)
{
int[] arr = { 0, -1, 2, -3, 1 };
int sum = -2;
int n = arr.Length;
findTriplets(arr, n, sum);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program to find triplets in a given
// array whose sum is equal to given sum.
// function to print triplets with given sum
function findTriplets(arr,n,sum)
{
for (let i = 0; i < n - 1; i++) {
// Find all pairs with sum equals to
// "sum-arr[i]"
let s = new Set();
for (let j = i + 1; j < n; j++) {
let x = sum - (arr[i] + arr[j]);
if (s.has(x))
document.write( x+" "+ arr[i]+" "+ arr[j]+"<br>");
else
s.add(arr[j]);
}
}
}
// Driver code
let arr=[0, -1, 2, -3, 1];
let sum = -2;
let n = arr.length;
findTriplets(arr, n, sum);
// This code is contributed by unknown2108
</script>
Producción:
-3 0 1 2 -1 -3
Análisis de Complejidad:
- Complejidad Temporal: O(n 2 ).
El uso de un bucle for anidado lleva la complejidad del tiempo a n 2 . - Espacio Auxiliar: O(n).
Como se ha utilizado una estructura de datos unordered_set para almacenar valores.
Método 3 : este método utiliza el método de clasificación y la técnica de dos punteros para resolver el problema anterior. Esta ejecución implicará una complejidad temporal O(n 2 )) y una complejidad espacial O(1). La idea se basa en el Método 2 de esta publicación.
Enfoque: la técnica de dos punteros se puede poner en práctica utilizando la técnica de clasificación. En la técnica de dos punteros, se puede buscar el par que tiene una suma objetivo en tiempo lineal . La idea aquí es fijar un puntero (por ejemplo, a) y usar los punteros restantes para encontrar el par que tiene la suma requerida del valor objetivo en (a) de manera eficiente.
Ahora analicemos cómo podemos encontrar el par requerido de manera efectiva utilizando la técnica de dos punteros. Los punteros utilizados para la técnica de dos punteros son, por ejemplo, (l y r) .
- Entonces, si la suma = valor (a) + valor (l) + valor (r) excede la suma requerida, para el mismo (a, l) el valor requerido (r) debe ser menor que el anterior. Por lo tanto, decrementando el puntero r .
- Si la suma = valor (a) + valor (l) + valor (r) es menor que la suma requerida, para el mismo (a, r) el valor requerido (l) debe ser mayor que el anterior. Por lo tanto, incrementando el puntero l .
Algoritmo:
- Ordene la array y para cada elemento arr[i] busque los otros dos elementos arr[l], arr[r] de modo que arr[i]+arr[l]+arr[r]=Target sum .
- La búsqueda de los otros dos elementos se puede realizar de manera eficiente utilizando la técnica de dos punteros a medida que se ordena la array.
- Ejecute un ciclo externo tomando la variable de control como i y para cada iteración inicialice un valor l que es el primer puntero con i+1 y r con el último índice.
- Ahora ingrese en un bucle while que se ejecutará hasta el valor de l<r .
- Si arr[i]+arr[l]+arr[r]>Target sum entonces disminuya r en 1 ya que la suma requerida es menor que la suma actual y disminuir el valor de hará lo necesario.
- Si arr[i]+arr[l]+arr[r]<Target sum entonces incremente l en 1 ya que la suma requerida es menor que la suma actual y aumentar el valor de hará lo necesario.
- Si arr[i]+arr[l]+arr[r]==Target sum imprime los valores.
- Incremento i Ir al Paso 3.
Pseudocódigo:
1. Sort all element of array
2. Run loop from i=0 to n-2.
Initialize two index variables l=i+1 and r=n-1
4. while (l < r)
Check sum of arr[i], arr[l], arr[r] is
given sum or not if sum is 'sum', then print
the triplet and do l++ and r--.
5. If sum is less than given sum then l++
6. If sum is greater than given sum then r--
7. If not exist in array then print not found.
C++
// C++ program to find triplets in a given
// array whose sum is given sum.
#include <bits/stdc++.h>
using namespace std;
// Function to print triplets with given sum
vector<vector<int>> findTriplets(int nums[],int n,int sumTarget) {
vector<vector<int>> res;
if(n <=2) return res;
sort(nums,nums + n);
for(int i=0;i<n;i++){
if(i>0 && nums[i] == nums[i-1]) // avoid duplicate triplets count
continue;
int num = nums[i];
int target = sumTarget - num;
for(int l=i+1, r=n-1; l<r; ) {
if(nums[l]+nums[r] > target)
r--;
else if (nums[l]+nums[r] < target)
l++;
else {
// nums[l] + nums[r] == target
res.push_back({nums[i], nums[l], nums[r]});
// skip duplicates
while( l<n-1 && nums[l]==nums[l+1]) l++;
while( r>0 && nums[r]==nums[r-1]) r--;
l++;
r--;
}
}
}
return res;
}
// Driver code
int main()
{
int arr[] = { 0, -1, 2, -3, 1, -1, 3, 0};
int sum = -2;
int n = sizeof(arr) / sizeof(arr[0]);
vector<vector<int>> res = findTriplets(arr, n, sum);
cout<<"Unique triplets found are : \n";
for(int i = 0;i<res.size();i++)
cout<<res[i][0]<<" "<<res[i][1]<<" "<<res[i][2]<<"\n";
return 0;
}
Java
// Java program to find triplets
// in a given array whose sum
// is given sum.
import java.io.*;
import java.util.*;
class GFG {
// function to print
// triplets with given sum
static void findTriplets(int[] arr,
int n, int sum)
{
// sort array elements
Arrays.sort(arr);
for (int i = 0;
i < n - 1; i++) {
// initialize left and right
int l = i + 1;
int r = n - 1;
int x = arr[i];
while (l < r) {
if (x + arr[l] + arr[r] == sum) {
// print elements if it's
// sum is given sum.
System.out.println(
x + " " + arr[l] + " "
+ arr[r]);
l++;
r--;
}
// If sum of three elements
// is less than 'sum' then
// increment in left
else if (x + arr[l] + arr[r] < sum)
l++;
// if sum is greater than
// given sum, then decrement
// in right side
else
r--;
}
}
}
// Driver code
public static void main(String args[])
{
int[] arr = new int[] { 0, -1, 2, -3, 1 };
int sum = -2;
int n = arr.length;
findTriplets(arr, n, sum);
}
}
// This code is contributed
// by Akanksha Rai(Abby_akku)
Python3
# Python3 program to find triplets in a # given array whose sum is given sum. # function to print triplets with # given sum def findTriplets(arr, n, sum): # sort array elements arr.sort(); for i in range(0, n - 1): # initialize left and right l = i + 1; r = n - 1; x = arr[i]; while (l < r) : if (x + arr[l] + arr[r] == sum) : # print elements if it's sum # is given sum. print(x, arr[l], arr[r]); l = l + 1; r = r - 1; # If sum of three elements is less # than 'sum' then increment in left elif (x + arr[l] + arr[r] < sum): l = l + 1; # if sum is greater than given sum, # then decrement in right side else: r = r - 1; # Driver code arr = [ 0, -1, 2, -3, 1 ]; sum = -2; n = len(arr); findTriplets(arr, n, sum); # This code is contributed by # Shivi_Aggarwal
C#
// C# program to find triplets
// in a given array whose sum
// is given sum.
using System;
class GFG {
// function to print
// triplets with given sum
static void findTriplets(int[] arr,
int n, int sum)
{
// sort array elements
Array.Sort(arr);
for (int i = 0; i < n - 1; i++) {
// initialize left and right
int l = i + 1;
int r = n - 1;
int x = arr[i];
while (l < r) {
if (x + arr[l] + arr[r] == sum) {
// print elements if it's
// sum is given sum.
Console.WriteLine(x + " " + arr[l] + " " + arr[r]);
l++;
r--;
}
// If sum of three elements
// is less than 'sum' then
// increment in left
else if (x + arr[l] + arr[r] < sum)
l++;
// if sum is greater than
// given sum, then decrement
// in right side
else
r--;
}
}
}
// Driver code
static int Main()
{
int[] arr = new int[] { 0, -1, 2, -3, 1 };
int sum = -2;
int n = arr.Length;
findTriplets(arr, n, sum);
return 0;
}
}
// This code is contributed by rahul
PHP
<?php
// PHP program to find triplets
// in a given array whose sum
// is given sum.
// function to print triplets
// with given sum
function findTriplets($arr, $n, $sum)
{
// sort array elements
sort($arr);
for ($i = 0; $i < $n - 1; $i++)
{
// initialize left and right
$l = $i + 1;
$r = $n - 1;
$x = $arr[$i];
while ($l < $r)
{
if ($x + $arr[$l] +
$arr[$r] == $sum)
{
// print elements if it's
// sum is given sum.
echo $x, " ", $arr[$l],
" ", $arr[$r], "\n";
$l++;
$r--;
}
// If sum of three elements
// is less than 'sum' then
// increment in left
else if ($x + $arr[$l] +
$arr[$r] < $sum)
$l++;
// if sum is greater
// than given sum, then
// decrement in right side
else
$r--;
}
}
}
// Driver code
$arr = array(0, -1, 2, -3, 1);
$sum = -2;
$n = sizeof($arr);
findTriplets($arr, $n, $sum);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to find triplets
// in a given array whose sum
// is given sum.
// function to print
// triplets with given sum
function findTriplets(arr, n, sum)
{
// sort array elements
arr.sort(function(a, b){return a - b});
for (let i = 0; i < n - 1; i++) {
// initialize left and right
let l = i + 1;
let r = n - 1;
let x = arr[i];
while (l < r) {
if (x + arr[l] + arr[r] == sum)
{
// print elements if it's
// sum is given sum.
document.write(x + " " + arr[l] + " " + arr[r] + "</br>");
l++;
r--;
}
// If sum of three elements
// is less than 'sum' then
// increment in left
else if (x + arr[l] + arr[r] < sum)
l++;
// if sum is greater than
// given sum, then decrement
// in right side
else
r--;
}
}
}
let arr = [ 0, -1, 2, -3, 1 ];
let sum = -2;
let n = arr.length;
findTriplets(arr, n, sum);
// This code is contributed by rameshtravel07.
</script>
Producción:
-3 -1 2 -3 0 1
Análisis de Complejidad:
- Complejidad Temporal: O(n 2 ).
El uso de un ciclo anidado (uno para iterar, otro para la técnica de dos punteros) lleva la complejidad del tiempo a O(n 2 ). - Espacio Auxiliar: O(1).
Como no se utiliza ninguna estructura de datos adicional.