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

<?php
// PHP 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
    sort($arr);
  
    // For every element in arr check 
    // if a pair exist(in array) whose
    // sum is equal to arr element
    for ($i = $n - 1; $i >= 0; $i--)
    {
        $j = 0;
        $k = $i - 1;
        while ($j < $k) 
        {
            if ($arr[$i] == $arr[$j] + $arr[$k]) 
            {                
                // Pair found
                echo "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
    echo "No such triplet exists";
}
  
// Driver Code
$arr = array(5, 32, 1, 7, 10, 
             50, 19, 21, 2 );
$n = count($arr);
findTriplet($arr, $n);
// This code is contributed by anuj_67.
?>

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.