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

# Python3 program to find a triplet 
# that sum to a given value
  
# returns true if there is triplet with
# sum equal to 'sum' present in A[]. 
# Also, prints the triplet
def find3Numbers(A, arr_size, sum):
  
    # Fix the first element as A[i]
    for i in range( 0, arr_size-2):
  
        # Fix the second element as A[j]
        for j in range(i + 1, arr_size-1): 
              
            # Now look for the third number
            for k in range(j + 1, arr_size):
                if A[i] + A[j] + A[k] == sum:
                    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 function 
A = [1, 4, 45, 6, 10, 8]
sum = 22
arr_size = len(A)
find3Numbers(A, arr_size, sum)
  
# This code is contributed by Smitha Dinesh Semwal 

Triplet is 4, 10, 8

• Análisis de Complejidad: 
  • Complejidad Temporal: O(n ³ ). 
    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:

# Python3 program to find a triplet
  
# returns true if there is triplet
# with sum equal to 'sum' present
# in A[]. Also, prints the triplet
def find3Numbers(A, arr_size, sum):
  
    # Sort the elements 
    A.sort()
  
    # Now fix the first element 
    # one by one and find the
    # other two elements 
    for i in range(0, arr_size-2):
      
  
        # To find the other two elements,
        # start two index variables from
        # two corners of the array and
        # move them toward each other
          
        # index of the first element
        # in the remaining elements
        l = i + 1 
          
        # index of the last element
        r = arr_size-1 
        while (l < r):
          
            if( A[i] + A[l] + A[r] == sum):
                print("Triplet is", A[i], 
                     ', ', A[l], ', ', A[r]);
                return True
              
            elif (A[i] + A[l] + A[r] < sum):
                l += 1
            else: # A[i] + A[l] + A[r] > sum
                r -= 1
  
    # If we reach here, then
    # no triplet was found
    return False
  
# Driver program to test above function 
A = [1, 4, 45, 6, 10, 8]
sum = 22
arr_size = len(A)
  
find3Numbers(A, arr_size, sum)
  
# This is contributed by Smitha Dinesh Semwal

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:

# Python3 program to find a triplet using Hashing
# returns true if there is triplet with sum equal
# to 'sum' present in A[]. Also, prints the triplet
def find3Numbers(A, arr_size, sum):
    for i in range(0, arr_size-1):
        # Find pair in subarray A[i + 1..n-1] 
        # with sum equal to sum - A[i]
        s = set()
        curr_sum = sum - A[i]
        for j in range(i + 1, arr_size):
            if (curr_sum - A[j]) in s:
                print("Triplet is", A[i], 
                        ", ", A[j], ", ", curr_sum-A[j])
                return True
            s.add(A[j])
      
    return False
  
# Driver program to test above function 
A = [1, 4, 45, 6, 10, 8] 
sum = 22
arr_size = len(A) 
find3Numbers(A, arr_size, sum) 
  
# This is contributed by Yatin gupta

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.