Programa Javascript 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:

<script>
// Javascript program to find three numbers
// such that sum of two makes the
// third element in array
  
// Utility function for finding
// triplet in array
function findTriplet(arr, n)
{
    // Sort the array
    arr.sort((a,b) => a-b);
  
    // For every element in arr check 
    // if a pair exist(in array) whose
    // sum is equal to arr element
    for (let i = n - 1; i >= 0; i--) 
    {
        let j = 0;
        let k = i - 1;
  
        // Iterate forward and backward to 
        // find the other two elements
        while (j < k) 
        {
            // If the two elements sum is
            // equal to the third element
            if (arr[i] == arr[j] + arr[k]) 
            {
                // Pair found
                document.write("numbers are " + arr[i] + 
                               " " + arr[j] + " " + 
                               arr[k] + "<br>");
                return;
            }
  
            // If the element is greater than
            // sum of both the elements, then try
            // adding a smaller number to reach the
            // equality
            else if (arr[i] > arr[j] + arr[k])
                j += 1;
  
            // If the element is smaller, then
            // try with a smaller number
            // to reach equality, so decrease K
            else
                k -= 1;
        }
    }
  
    // No such triplet is found in array
    document.write("No such triplet exists");
}
  
// Driver code
let arr = [5, 32, 1, 7, 10, 50, 19, 21, 2];
let n = arr.length;
findTriplet(arr, n);
// This code is contributed by Mayank Tyagi
</script>

Producción:  

numbers are 21 2 19

Complejidad del tiempo : O(N^2)

Otro enfoque: la idea es similar al enfoque anterior.

1. Ordenar la array dada.
2. Inicie un bucle anidado, fijando el primer elemento i (de 0 a n-1) y moviendo el otro j (de i+1 a n-1).
3. Tome la suma de ambos elementos y búsquelo en la array restante usando la búsqueda binaria.

<script>
// Javascript program to find three numbers
// such that sum of two makes the
// third element in array
  
bool search(sum, start, end, arr)
{
    while (start <= end) 
    {
        let mid = (start + end) / 2;
        if (arr[mid] == sum) 
        {
            return true;
        }
        else if (arr[mid] > sum) 
        {
            end = mid - 1;
        }
        else 
        {
            start = mid + 1;
        }
    }
    return false;
}
  
// Utility function for finding
// triplet in array
function findTriplet(arr, n)
{
    // Sort the array
    arr.sort((a,b) => a-b);
  
    // Initialising nested loops
    for (let i = 0; i < n; i++) 
    {
        for (let j = i + 1; j < n; j++) 
        {
            if (search((arr[i] + arr[j]), 
                j, n - 1, arr)) 
            {
                document.write("numbers are " + arr[i] +
                               " " + arr[j] + " " + 
                              ( arr[i] + arr[j] ) + "<br>");
            }
        }
    }
    // No such triplet is found in array
    document.write("No such triplet exists");
}
  
// Driver code
let arr = [5, 32, 1, 7, 10, 50, 19, 21, 2];
let n = arr.length;
findTriplet(arr, n);
</script>
// This code is contributed by Sarthak Delori

Complejidad del tiempo: O(N^2*log N)

Complejidad espacial:   O(1)

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.