Programa Java para encontrar un triplete tal que la suma de dos sea igual al tercer elemento

Dada una array de números enteros, debe encontrar tres números tales que la suma de dos elementos sea igual al tercer elemento.
Ejemplos:

Input: {5, 32, 1, 7, 10, 50, 19, 21, 2}
Output: 21, 2, 19

Input: {5, 32, 1, 7, 10, 50, 19, 21, 0}
Output: no such triplet exist

Fuente de la pregunta: experiencia de entrevista con Arcesium | Conjunto 7 (En el campus para prácticas)

Enfoque simple: ejecute tres bucles y verifique si existe un triplete tal que la suma de dos elementos sea igual al tercer elemento.
Complejidad del tiempo : O(n^3)
Enfoque eficiente: La idea es similar a Encontrar un triplete que sume un valor dado.

• Primero ordene la array dada.
• Comience a fijar el mayor elemento de tres desde atrás y recorra la array para encontrar los otros dos números que suman el tercer elemento.
• Tome dos punteros j (desde el frente) y k (inicialmente i-1) para encontrar el menor de los dos números y desde i-1 para encontrar el mayor de los dos números restantes
• Si la suma de ambos números sigue siendo menor que A[i], entonces necesitamos aumentar el valor de la suma de dos números, aumentando así el puntero j, para aumentar el valor de A[j] + A[ k] .
• Si la suma de ambos números es mayor que A[i], entonces debemos disminuir el valor de la suma de dos números, por lo tanto, disminuir el puntero k para disminuir el valor total de A[j] + A[k ] .

La imagen de abajo es una ejecución en seco del enfoque anterior:

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

// Java program to find three numbers
// such that sum of two makes the
// third element in array
import java.util.Arrays;
  
public class GFG 
{
    // Utility function for finding
    // triplet in array
    static void findTriplet(int arr[], int n)
    {
        // Sort the array
        Arrays.sort(arr);
  
        // For every element in arr check 
        // if a pair exist(in array) whose
        // sum is equal to arr element
        for (int i = n - 1; i >= 0; i--) 
        {
            int j = 0;
            int k = i - 1;
            while (j < k) {
                if (arr[i] == arr[j] + arr[k]) 
                {
                    // Pair found
                    System.out.println("numbers are " + arr[i] + 
                                       " " + arr[j] + " " + arr[k]);
                    return;
                }
                else if (arr[i] > arr[j] + arr[k])
                    j += 1;
                else
                    k -= 1;
            }
        }
  
        // No such triplet is found in array
        System.out.println("No such triplet exists");
    }
  
    // Driver code
    public static void main(String args[])
    {
        int arr[] = {5, 32, 1, 7, 10, 
                     50, 19, 21, 2};
        int n = arr.length;
        findTriplet(arr, n);
    }
}
// This code is contributed by Sumit Ghosh

Producción:  

numbers are 21 2 19

Complejidad de tiempo : O (N ^ 2)
Consulte el artículo completo sobre Encontrar un triplete tal que la suma de dos sea igual al tercer elemento para obtener más detalles.