Dada una array y un valor de suma, encuentre todos los tripletes únicos posibles en esa array cuya suma sea igual al valor de suma dado. Si no se pueden formar dichos tripletes a partir de la array, imprima «No se pueden formar tripletes», de lo contrario, imprima todos los tripletes únicos. Por ejemplo, si la array dada es {12, 3, 6, 1, 6, 9} y la suma dada es 24, entonces los tripletes únicos son (3, 9, 12) y (6, 6, 12) cuya suma es 24
Ejemplos:
Input : array = {12, 3, 6, 1, 6, 9} sum = 24
Output : [[3, 9, 12], [6, 6, 12]]
Input : array = {-2, 0, 1, 1, 2} sum = 0
Output : [[-2, 0, 2], [-2, 1, 1]]
Input : array = {-2, 0, 1, 1, 2} sum = 10
Output : No triplets can be formed
Método 1
En una publicación anterior, encuentre un triplete que sume un valor dado, hemos discutido si los tripletes se pueden formar a partir de la array o no.
Aquí necesitamos imprimir todos los conjuntos únicos de trillizos que suman un valor dado
- Ordenar la array de entrada.
- Encuentre tres índices de la array i, j y k donde A[i]+A[j]+A[k] = valor de suma dado.
- Arregle el primer elemento como A[i] e itere i desde 0 hasta el tamaño de la array – 2.
- Para cada iteración de i, tome j como el índice del primer elemento en los elementos restantes y k como el índice del último elemento.
- Compruebe la combinación de triplete A[i]+A[j]+A[k] = valor de suma dado.
- Si se obtiene el triplete (es decir, A[i]+A[j]+A[k] = valor de suma dado)
- Agregue todo el triplete en un TreeSet con un valor separado por «:» para obtener los tripletes únicos.
- Incrementar el índice del segundo valor
- Decrementa el índice del tercer valor.
- Repita los pasos 4 y 5 hasta j < k
- De lo contrario, si, A[i]+A[j]+A[k] < valor de suma dado, incrementa el índice del segundo valor De
lo contrario, si, A[i]+A[j]+A[k] > valor de suma dado, decrementa el índice del tercer valor
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to find unique triplets
// that sum up to a given value.
#include <bits/stdc++.h>
using namespace std;
// Structure to define a triplet.
struct triplet
{
int first, second, third;
};
// Function to find unique triplets that
// sum up to a given value.
int findTriplets(int nums[], int n, int sum)
{
int i, j, k;
// Vector to store all unique triplets.
vector<triplet> triplets;
// Set to store already found triplets
// to avoid duplication.
unordered_set<string> uniqTriplets;
// Variable used to hold triplet
// converted to string form.
string temp;
// Variable used to store current
// triplet which is stored in vector
// if it is unique.
triplet newTriplet;
// Sort the input array.
sort(nums, nums + n);
// Iterate over the array from the
// start and consider it as the
// first element.
for (i = 0; i < n - 2; i++)
{
// index of the first element in
// the remaining elements.
j = i + 1;
// index of the last element.
k = n - 1;
while (j < k) {
// If sum of triplet is equal to
// given value, then check if
// this triplet is unique or not.
// To check uniqueness, convert
// triplet to string form and
// then check if this string is
// present in set or not. If
// triplet is unique, then store
// it in vector.
if (nums[i] + nums[j] + nums[k] == sum)
{
temp = to_string(nums[i]) + " : "
+ to_string(nums[j]) + " : "
+ to_string(nums[k]);
if (uniqTriplets.find(temp)
== uniqTriplets.end()) {
uniqTriplets.insert(temp);
newTriplet.first = nums[i];
newTriplet.second = nums[j];
newTriplet.third = nums[k];
triplets.push_back(newTriplet);
}
// Increment the first index
// and decrement the last
// index of remaining elements.
j++;
k--;
}
// If sum is greater than given
// value then to reduce sum
// decrement the last index.
else if (nums[i] + nums[j] + nums[k] > sum)
k--;
// If sum is less than given value
// then to increase sum increment
// the first index of remaining
// elements.
else
j++;
}
}
// If no unique triplet is found, then
// return 0.
if (triplets.size() == 0)
return 0;
// Print all unique triplets stored in
// vector.
for (i = 0; i < triplets.size(); i++) {
cout << "[" << triplets[i].first << ", "
<< triplets[i].second << ", "
<< triplets[i].third << "], ";
}
}
// Driver Code
int main()
{
int nums[] = { 12, 3, 6, 1, 6, 9 };
int n = sizeof(nums) / sizeof(nums[0]);
int sum = 24;
// Function call
if (!findTriplets(nums, n, sum))
cout << "No triplets can be formed.";
return 0;
}
// This code is contributed by NIKHIL JINDAL.
Java
// Java program to find all triplets with given sum
import java.util.*;
public class triplets {
// returns all triplets whose sum is
// equal to sum value
public static List<List<Integer> >
findTriplets(int[] nums, int sum)
{
/* Sort the elements */
Arrays.sort(nums);
List<List<Integer> > pair
= new ArrayList<>();
TreeSet<String> set
= new TreeSet<String>();
List<Integer> triplets
= new ArrayList<>();
/* Iterate over the array from the start
and consider it as the first element*/
for (int i = 0;
i < nums.length - 2;
i++) {
// index of the first element in the
// remaining elements
int j = i + 1;
// index of the last element
int k = nums.length - 1;
while (j < k) {
if (nums[i] + nums[j]
+ nums[k] == sum) {
String str
= nums[i] + ":" + nums[j]
+ ":" + nums[k];
if (!set.contains(str))
{
// To check for the unique triplet
triplets.add(nums[i]);
triplets.add(nums[j]);
triplets.add(nums[k]);
pair.add(triplets);
triplets = new ArrayList<>();
set.add(str);
}
// increment the second value index
j++;
// decrement the third value index
k--;
}
else if (nums[i]
+ nums[j]
+ nums[k] < sum)
j++;
else
k--;
}
}
return pair;
}
// Driver code
public static void main(String[] args)
{
int[] nums = { 12, 3, 6, 1, 6, 9 };
int sum = 24;
List<List<Integer> > triplets
= findTriplets(nums, sum);
// Function call
if (!triplets.isEmpty()) {
System.out.println(triplets);
}
else {
System.out.println("No triplets can be formed");
}
}
}
Python3
# Python program to find unique triplets
# that sum up to a given value.
# Function to find unique triplets that
# sum up to a given value.
def findTriplets(nums, n, Sum):
i = 0
j = 0
k = 0
# list to store all unique triplets.
triplet = []
# list to store already found triplets
# to avoid duplication.
uniqTriplets = []
# Variable used to hold triplet
# converted to string form.
temp = ""
# Variable used to store current
# triplet which is stored in vector
# if it is unique.
newTriplet = [0, 0, 0]
# Sort the input array.
nums.sort()
# Iterate over the array from the
# start and consider it as the
# first element.
for i in range(n - 2):
# index of the first element in
# the remaining elements.
j = i + 1
# index of the last element.
k = n - 1
while(j < k):
# If sum of triplet is equal to
# given value, then check if
# this triplet is unique or not.
# To check uniqueness, convert
# triplet to string form and
# then check if this string is
# present in set or not. If
# triplet is unique, then store
# it in list.
if(nums[i] + nums[j] + nums[k] == Sum):
temp = str(nums[i]) + ":" + str(nums[j]) + ":" + str(nums[k])
if temp not in uniqTriplets:
uniqTriplets.append(temp)
newTriplet[0] = nums[i]
newTriplet[1] = nums[j]
newTriplet[2] = nums[k]
triplet.append(newTriplet)
newTriplet = [0, 0, 0]
# Increment the first index
# and decrement the last
# index of remaining elements.
j += 1
k -= 1
# If sum is greater than given
# value then to reduce sum
# decrement the last index.
elif(nums[i] + nums[j] + nums[k] > Sum):
k -= 1
# If sum is less than given value
# then to increase sum increment
# the first index of remaining
# elements.
else:
j += 1
# If no unique triplet is found, then
# return 0.
if(len(triplet) == 0):
return 0
# Print all unique triplets stored in
# list.
for i in range(len(triplet)):
print(triplet[i], end = ", ")
return 1
# Driver Code
nums = [12, 3, 6, 1, 6, 9]
n = len(nums)
Sum = 24
# Function call
if(not findTriplets(nums, n, Sum)):
print("No triplets can be formed.")
# This code is contributed by rag2127
C#
// C# program to find all triplets with given sum
using System;
using System.Collections.Generic;
class GFG {
// returns all triplets whose sum is
// equal to sum value
public static List<List<int>>
findTriplets(int[] nums,int sum)
{
/* Sort the elements */
Array.Sort(nums);
List<List<int> > pair
= new List<List<int> >();
SortedSet<String> set
= new SortedSet<String>();
List<int> triplets
= new List<int>();
/* Iterate over the array from the start and
consider it as the first element*/
for (int i = 0;
i < nums.Length - 2;
i++) {
// index of the first element in the
// remaining elements
int j = i + 1;
// index of the last element
int k = nums.Length - 1;
while (j < k) {
if (nums[i]
+ nums[j]
+ nums[k] == sum) {
String str
= nums[i] + ":" + nums[j]
+ ":" + nums[k];
if (!set.Contains(str))
{
// To check for the unique triplet
triplets.Add(nums[i]);
triplets.Add(nums[j]);
triplets.Add(nums[k]);
pair.Add(triplets);
triplets = new List<int>();
set.Add(str);
}
j++; // increment the second value index
k--; // decrement the third value index
}
else if (nums[i]
+ nums[j]
+ nums[k] < sum)
j++;
else
k--;
}
}
return pair;
}
// Driver Code
public static void Main(String[] args)
{
int[] nums = { 12, 3, 6, 1, 6, 9 };
int sum = 24;
List<List<int> > triplets
= findTriplets(nums, sum);
// Function call
if (triplets.Count != 0) {
Console.Write("[");
for (int i = 0; i < triplets.Count; i++)
{
List<int> l = triplets[i];
Console.Write("[");
for (int j = 0; j < l.Count; j++)
{
Console.Write(l[j]);
if (l.Count != j + 1)
Console.Write(", ");
}
Console.Write("]");
if (triplets.Count != i + 1)
Console.Write(",");
}
Console.Write("]");
}
else
{
Console.WriteLine("No triplets can be formed");
}
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to find all triplets with given sum
// returns all triplets whose sum is
// equal to sum value
function findTriplets(nums,sum)
{
/* Sort the elements */
nums.sort(function(a,b){return a-b;});
let pair = [];
let set = new Set();
let triplets= [];
//let newTriplet = [0, 0, 0];
for (let i = 0;
i < nums.length - 2;
i++)
{
// index of the first element in the
// remaining elements
let j = i + 1;
// index of the last element
let k = nums.length - 1;
while (j < k) {
if (nums[i] + nums[j]
+ nums[k] == sum) {
let str= nums[i] + ":" + nums[j]
+ ":" + nums[k];
if (!set.has(str))
{
// To check for the unique triplet
triplets.push(nums[i]);
triplets.push(nums[j]);
triplets.push(nums[k]);
pair.push(triplets);
triplets =[];
set.add(str);
}
// increment the second value index
j++;
// decrement the third value index
k--;
}
else if (nums[i]
+ nums[j]
+ nums[k] < sum)
j++;
else
k--;
}
}
return pair;
}
// Driver code
let nums=[12, 3, 6, 1, 6, 9];
let sum = 24;
let triplets
= findTriplets(nums, sum);
// Function call
if (triplets.length!=0) {
document.write("[");
for (let i = 0; i < triplets.length; i++)
{
let l = triplets[i];
document.write("[");
for (let j = 0; j < l.length; j++)
{
document.write(l[j]);
if (l.length != j + 1)
document.write(", ");
}
document.write("]");
if (triplets.length != i + 1)
document.write(", ");
}
document.write("]");
}
else {
document.write("No triplets can be formed");
}
//This code is contributed by avanitrachhadiya2155
</script>
Producción
[3, 9, 12], [6, 6, 12],
Complejidad de tiempo: O(n 2 )
Complejidad de espacio : O(n)
Método 2
En este método, veremos otra forma de resolver este problema que utilizará solo una cantidad constante de espacio. Aquí, en este método, verificaríamos si el elemento actual es el mismo que el anterior, entonces no lo consideraremos y simplemente omitiremos ese elemento. Al usar esto, podremos encontrar solo trillizos únicos.
Algoritmo
- Ordenar la array de entrada.
- Para el primer elemento iterar i de 0 a n-2.
- Para cada iteración tendremos dos índices de inicio y final donde el inicio sería igual a i+1 y el final sería igual a n-1.
- Ahora buscaremos un objetivo cuyo valor sea sum-a[i] en el rango de principio a fin usando dos técnicas de puntero.
- En esto buscaremos los elementos anteriores si son iguales entonces no trabajaríamos para ellos para encontrar todos los duplicados únicos.
- Si encontráramos target==a[start]+a[end] entonces lo imprimiríamos e incrementaríamos start y decrementar end.
- Si target>a[start]+a[end] entonces incrementaríamos start.
- De lo contrario, disminuiríamos el final
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to find all unique triplets
// without using any extra space.
#include <bits/stdc++.h>
using namespace std;
// Function to all find unique triplets
// without using extra space
void findTriplets(int a[], int n, int sum)
{
int i;
// Sort the input array
sort(a, a + n);
// For handling the cases when no such
// triplets exits.
bool flag = false;
// Iterate over the array from start to n-2.
for (i = 0; i < n - 2; i++)
{
if (i == 0 || a[i] > a[i - 1])
{
// Index of the first element in
// remaining range.
int start = i + 1;
// Index of the last element
int end = n - 1;
// Setting our new target
int target = sum - a[i];
while (start < end)
{
// Checking if current element
// is same as previous
if (start > i + 1
&& a[start] == a[start - 1])
{
start++;
continue;
}
// Checking if current element is
// same as previous
if (end < n - 1
&& a[end] == a[end + 1])
{
end--;
continue;
}
// If we found the triplets then print it
// and set the flag
if (target == a[start] + a[end])
{
cout << "[" << a[i]
<< "," << a[start]
<< "," << a[end] << "] ";
flag = true;
start++;
end--;
}
// If target is greater then
// increment the start index
else if (target > (a[start] + a[end]))
{
start++;
}
// If target is smaller than
// decrement the end index
else {
end--;
}
}
}
}
// If no such triplets found
if (flag == false) {
cout << "No Such Triplets Exist"
<< "\n";
}
}
// Driver code
int main()
{
int a[] = { 12, 3, 6, 1, 6, 9 };
int n = sizeof(a) / sizeof(a[0]);
int sum = 24;
// Function call
findTriplets(a, n, sum);
return 0;
}
// This code is contributed by Rohit
Java
// Java program to find all unique triplets
// without using any extra space.
import java.util.*;
public class Main
{
// Function to all find unique triplets
// without using extra space
public static void findTriplets(int a[], int n, int sum)
{
int i;
// Sort the input array
Arrays.sort(a);
// For handling the cases when no such
// triplets exits.
boolean flag = false;
// Iterate over the array from start to n-2.
for (i = 0; i < n - 2; i++)
{
if (i == 0 || a[i] > a[i - 1])
{
// Index of the first element in
// remaining range.
int start = i + 1;
// Index of the last element
int end = n - 1;
// Setting our new target
int target = sum - a[i];
while (start < end)
{
// Checking if current element
// is same as previous
if (start > i + 1
&& a[start] == a[start - 1])
{
start++;
continue;
}
// Checking if current element is
// same as previous
if (end < n - 1
&& a[end] == a[end + 1])
{
end--;
continue;
}
// If we found the triplets then print it
// and set the flag
if (target == a[start] + a[end])
{
System.out.print("[" + a[i]
+ "," + a[start]
+ "," + a[end] + "] ");
flag = true;
start++;
end--;
}
// If target is greater then
// increment the start index
else if (target > (a[start] + a[end]))
{
start++;
}
// If target is smaller than
// decrement the end index
else {
end--;
}
}
}
}
// If no such triplets found
if (flag == false) {
System.out.print("No Such Triplets Exist");
}
}
public static void main(String[] args) {
int a[] = { 12, 3, 6, 1, 6, 9 };
int n = a.length;
int sum = 24;
// Function call
findTriplets(a, n, sum);
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program to find all
# unique triplets without using
# any extra space.
# Function to all find unique
# triplets without using extra
# space
def findTriplets(a, n, sum):
# Sort the input array
a.sort()
# For handling the cases
# when no such triplets exits.
flag = False
# Iterate over the array from
# start to n-2.
for i in range(n - 2):
if (i == 0 or
a[i] > a[i - 1]):
# Index of the first
# element in remaining
# range.
start = i + 1
# Index of the last
# element
end = n - 1
# Setting our new target
target = sum - a[i]
while (start < end):
# Checking if current element
# is same as previous
if (start > i + 1 and
a[start] == a[start - 1]):
start += 1
continue
# Checking if current
# element is same as
# previous
if (end < n - 1 and
a[end] == a[end + 1]):
end -= 1
continue
# If we found the triplets
# then print it and set the
# flag
if (target == a[start] + a[end]):
print("[", a[i], ",",
a[start], ",",
a[end], "]",
end = " ")
flag = True
start += 1
end -= 1
# If target is greater then
# increment the start index
elif (target >
(a[start] + a[end])):
start += 1
# If target is smaller than
# decrement the end index
else:
end -= 1
# If no such triplets found
if (flag == False):
print("No Such Triplets Exist")
# Driver code
if __name__ == "__main__":
a = [12, 3, 6, 1, 6, 9]
n = len(a)
sum = 24
# Function call
findTriplets(a, n, sum)
# This code is contributed by Chitranayal
C#
// C# program to find all unique triplets
// without using any extra space.
using System;
using System.Collections.Generic;
class GFG {
// Function to all find unique triplets
// without using extra space
static void findTriplets(int[] a, int n, int sum)
{
int i;
// Sort the input array
Array.Sort(a);
// For handling the cases when no such
// triplets exits.
bool flag = false;
// Iterate over the array from start to n-2.
for (i = 0; i < n - 2; i++)
{
if (i == 0 || a[i] > a[i - 1])
{
// Index of the first element in
// remaining range.
int start = i + 1;
// Index of the last element
int end = n - 1;
// Setting our new target
int target = sum - a[i];
while (start < end)
{
// Checking if current element
// is same as previous
if (start > i + 1
&& a[start] == a[start - 1])
{
start++;
continue;
}
// Checking if current element is
// same as previous
if (end < n - 1
&& a[end] == a[end + 1])
{
end--;
continue;
}
// If we found the triplets then print it
// and set the flag
if (target == a[start] + a[end])
{
Console.Write("[" + a[i]
+ "," + a[start]
+ "," + a[end] + "] ");
flag = true;
start++;
end--;
}
// If target is greater then
// increment the start index
else if (target > (a[start] + a[end]))
{
start++;
}
// If target is smaller than
// decrement the end index
else {
end--;
}
}
}
}
// If no such triplets found
if (flag == false) {
Console.WriteLine("No Such Triplets Exist");
}
}
static void Main() {
int[] a = { 12, 3, 6, 1, 6, 9 };
int n = a.Length;
int sum = 24;
// Function call
findTriplets(a, n, sum);
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// Javascript program to find all unique triplets
// without using any extra space.
// Function to all find unique triplets
// without using extra space
function findTriplets(a, n, sum)
{
let i;
// Sort the input array
a.sort(function(a, b){return a - b});
// For handling the cases when no such
// triplets exits.
let flag = false;
// Iterate over the array from start to n-2.
for (i = 0; i < n - 2; i++)
{
if (i == 0 || a[i] > a[i - 1])
{
// Index of the first element in
// remaining range.
let start = i + 1;
// Index of the last element
let end = n - 1;
// Setting our new target
let target = sum - a[i];
while (start < end)
{
// Checking if current element
// is same as previous
if (start > i + 1
&& a[start] == a[start - 1])
{
start++;
continue;
}
// Checking if current element is
// same as previous
if (end < n - 1
&& a[end] == a[end + 1])
{
end--;
continue;
}
// If we found the triplets then print it
// and set the flag
if (target == a[start] + a[end])
{
document.write("[" + a[i]
+ "," + a[start]
+ "," + a[end] + "] ");
flag = true;
start++;
end--;
}
// If target is greater then
// increment the start index
else if (target > (a[start] + a[end]))
{
start++;
}
// If target is smaller than
// decrement the end index
else {
end--;
}
}
}
}
// If no such triplets found
if (flag == false) {
document.write("No Such Triplets Exist");
}
}
let a = [ 12, 3, 6, 1, 6, 9 ];
let n = a.length;
let sum = 24;
// Function call
a.sort();
findTriplets(a, n, sum);
// This code is contributed by suresh07.
</script>
Producción
[3,9,12] [6,6,12]
Análisis de Complejidad:
- Complejidad Temporal: O(n 2 ).
Dado que se requieren dos bucles anidados, la complejidad del tiempo es O(n 2 ). - Espacio Auxiliar: O(1).
Dado que no necesitamos espacio adicional para resolver esto.
Este artículo es una contribución de Aarthi C. Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a contribuido@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA