Programa de Python 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:

# Python program to find three numbers
# such that sum of two makes the
# third element in array
  
# Utility function for finding
# triplet in array
def findTriplet(arr, n):
      
    # Sort the array
    arr.sort()
   
    # For every element in arr check 
    # if a pair exist(in array) whose
    # sum is equal to arr element
    i = n - 1
    while(i >= 0):
        j = 0
        k = i - 1
        while (j < k):
            if (arr[i] == arr[j] + arr[k]):
                 
                # Pair found
                print "numbers are ", arr[i], 
                       arr[j], arr[k]
                return
            elif (arr[i] > arr[j] + arr[k]):
                j += 1
            else:
                k -= 1
        i -= 1
          
    # No such triplet is found in array
    print "No such triplet exists"
   
# Driver code
arr = [5, 32, 1, 7, 10, 50, 19, 21, 2]
n = len(arr)
findTriplet(arr, n)
# This code is contributed by Sachin Bisht

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.