Programa Java para encontrar un triplete que sume un valor dado

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: 
    1. Dada una array de longitud n y una suma s
    2. 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)
    3. El contador de estos bucles representa el índice de 3 elementos de los tripletes.
    4. Halla la suma de los elementos i, j y k. Si la suma es igual a la suma dada. Imprime el triplete y rompe.
    5. 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.

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: 
    1. Ordenar la array dada.
    2. Recorra la array y fije el primer elemento del posible triplete, arr[i].
    3. Luego fije dos punteros, uno en i + 1 y el otro en n – 1. Y mire la suma, 
      1. Si la suma es menor que la suma requerida, incremente el primer puntero.
      2. De lo contrario, si la suma es mayor, disminuya el puntero final para reducir la suma.
      3. 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.

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: 
    1. Atraviesa la array de principio a fin. (contador de bucle i)
    2. Cree un HashMap o configúrelo para almacenar pares únicos.
    3. Ejecute otro ciclo desde i+1 hasta el final de la array. (contador de bucle j)
    4. 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
    5. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *