Dada una array y un valor, encuentre si hay un triplete en la array cuya suma es igual al valor dado. Si hay tal triplete presente en la array, imprima el triplete y devuelva verdadero. De lo contrario, devuelve falso.
Ejemplos:
Entrada: array = {12, 3, 4, 1, 6, 9}, suma = 24;
Salida: 12, 3, 9
Explicación: Hay un triplete (12, 3 y 9) presente
en la array cuya suma es 24.
Entrada: array = {1, 2, 3, 4, 5}, suma = 9
Salida: 5, 3, 1
Explicación: Hay un triplete (5, 3 y 1) presente
en el arreglo cuya suma es 9.
Método 1 : Este es el enfoque ingenuo para resolver el problema anterior.
- Enfoque: 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 usando tres bucles anidados.
- Algoritmo:
- Dada una array de longitud n y una suma s
- Cree tres bucles anidados: el primer bucle se ejecuta de principio a fin (contador de bucle i), el segundo bucle se ejecuta desde i+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 tripletes.
- Halla la suma de los elementos i, j y k. Si la suma es igual a la suma dada. Imprime el triplete y rompe.
- Si no hay triplete, imprima que no existe triplete.
- Implementación:
Java
// 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;
// Fix the first element as A[i]
for (int i = 0; i < arr_size - 2; i++) {
// Fix the second element as A[j]
for (int j = i + 1; j < arr_size - 1; j++) {
// Now look for the third number
for (int k = j + 1; k < arr_size; k++) {
if (A[i] + A[j] + A[k] == sum) {
System.out.print("Triplet is " + A[i] + ", " + A[j] + ", " + A[k]);
return true;
}
}
}
}
// If we reach here, then no triplet was found
return false;
}
// Driver program to test above functions
public static void main(String[] args)
{
FindTriplet triplet = new FindTriplet();
int A[] = { 1, 4, 45, 6, 10, 8 };
int sum = 22;
int arr_size = A.length;
triplet.find3Numbers(A, arr_size, sum);
}
}
Producción
Triplet is 4, 10, 8
- Análisis de Complejidad:
- Complejidad Temporal: O(n 3 ).
Hay tres bucles anidados que atraviesan la array, por lo que la complejidad del tiempo es O (n ^ 3) - Complejidad espacial: O(1).
Como no se requiere espacio adicional.
- Complejidad Temporal: O(n 3 ).
Método 2: este método utiliza la clasificación para aumentar la eficiencia del código.
- Enfoque: al ordenar la array, se puede mejorar la eficiencia del algoritmo. Este enfoque eficiente utiliza la técnica de dos puntos . Atraviese la array y fije el primer elemento del triplete. Ahora use el algoritmo Two Pointers para encontrar si hay un par cuya suma es igual a x – array[i]. El algoritmo de dos punteros toma un tiempo lineal, por lo que es mejor que un bucle anidado.
- Algoritmo:
- Ordenar la array dada.
- Recorra la array y fije el primer elemento del posible triplete, arr[i].
- Luego fije dos punteros, uno en i + 1 y el otro en n – 1. Y mire 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 rompa.
- Implementación:
Java
// 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 < 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
r = arr_size - 1; // index of the last element
while (l < r) {
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] < sum)
l++;
else // A[i] + A[l] + A[r] > sum
r--;
}
}
// If we reach here, then no triplet was found
return false;
}
int partition(int A[], int si, int ei)
{
int x = A[ei];
int i = (si - 1);
int j;
for (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 to be sorted
si --> Starting index
ei --> Ending index
*/
void quickSort(int A[], int si, int ei)
{
int pi;
/* Partitioning index */
if (si < ei) {
pi = partition(A, si, ei);
quickSort(A, si, pi - 1);
quickSort(A, pi + 1, ei);
}
}
// Driver program to test above functions
public static void main(String[] args)
{
FindTriplet triplet = new FindTriplet();
int A[] = { 1, 4, 45, 6, 10, 8 };
int sum = 22;
int arr_size = A.length;
triplet.find3Numbers(A, arr_size, sum);
}
}
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 array, por lo que la complejidad del tiempo es O (n ^ 2). El algoritmo de dos punteros toma un tiempo O (n) y el primer elemento se puede arreglar usando otro recorrido anidado. - Complejidad espacial: O(1).
Como no se requiere espacio adicional.
- Complejidad del tiempo: O(N^2).
Método 3 : Esta es una solución basada en Hashing.
- Enfoque: este enfoque utiliza espacio adicional pero es más simple que el enfoque de dos puntos. Ejecute dos bucles, el bucle externo de principio a fin y el bucle interno desde i+1 hasta el final. Cree un hashmap o configure para almacenar los elementos entre i+1 y j-1. Entonces, si la suma dada es x, verifique si hay un número en el conjunto que sea igual a x – arr[i] – arr[j]. En caso afirmativo, imprima el triplete.
- Algoritmo:
- Atraviesa la array de principio a fin. (contador de bucle i)
- Cree un HashMap o configúrelo para almacenar pares únicos.
- Ejecute otro ciclo desde i+1 hasta el final de la array. (contador de bucle j)
- Si hay un elemento en el conjunto que es igual a x-arr[i] – arr[j], imprima el triplete (arr[i], arr[j], x-arr[i]-arr[j] ) y romper
- Inserta el j-ésimo elemento en el conjunto.
- Implementación:
Java
// Java program to find a triplet using Hashing
import java.util.*;
class GFG {
// returns true if there is triplet
// with sum equal to 'sum' present
// in A[]. Also, prints the triplet
static boolean find3Numbers(int A[],
int arr_size, int sum)
{
// Fix the first element as A[i]
for (int i = 0; i < arr_size - 2; i++) {
// Find pair in subarray A[i+1..n-1]
// with sum equal to sum - A[i]
HashSet<Integer> s = new HashSet<Integer>();
int curr_sum = sum - A[i];
for (int j = i + 1; j < arr_size; j++)
{
if (s.contains(curr_sum - A[j]))
{
System.out.printf("Triplet is %d,
%d, %d", A[i],
A[j], curr_sum - A[j]);
return true;
}
s.add(A[j]);
}
}
// If we reach here, then no triplet was found
return false;
}
/* Driver code */
public static void main(String[] args)
{
int A[] = { 1, 4, 45, 6, 10, 8 };
int sum = 22;
int arr_size = A.length;
find3Numbers(A, arr_size, sum);
}
}
// This code has been contributed by 29AjayKumar
Producción:
Triplet is 4, 8, 10
Complejidad temporal: O(N^2)
Espacio auxiliar: O(N)
Consulte el artículo completo sobre Encuentre un triplete que sume un valor dado para obtener más detalles.
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