Programa Python3 para encontrar todos los tripletes con suma cero

Dada una serie de elementos distintos. La tarea es encontrar tripletas en la array cuya suma sea cero.

Ejemplos: 

Input : arr[] = {0, -1, 2, -3, 1}
Output : (0 -1 1), (2 -3 1)

Explanation : The triplets with zero sum are
0 + -1 + 1 = 0 and 2 + -3 + 1 = 0  

Input : arr[] = {1, -2, 1, 0, 5}
Output : 1 -2  1
Explanation : The triplets with zero sum is
1 + -2 + 1 = 0   

Método 1: Este es un método simple que toma O(n ³ ) tiempo para llegar al resultado.

• Enfoque: el enfoque ingenuo ejecuta tres bucles y verifica uno por uno que la suma de los tres elementos es cero o no. Si la suma de tres elementos es cero, imprima los elementos; de lo contrario, imprima no encontrado.
• Algoritmo: 
  1. Ejecute tres bucles anidados con el contador de bucles i , j , k
  2. Los primeros bucles se ejecutarán de 0 a n-3 y el segundo bucle de i+1 a n-2 y el tercer bucle de j+1 a n-1. El contador de bucle representa los tres elementos del triplete.
  3. Compruebe si la suma de los elementos en i’th, j’th, k’th es igual a cero o no. En caso afirmativo, imprima la suma; de lo contrario, continúe.

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

# A simple Python 3 program 
# to find three elements whose 
# sum is equal to zero
  
# Prints all triplets in 
# arr[] with 0 sum
def findTriplets(arr, n):
  
    found = False
    for i in range(0, n-2):
      
        for j in range(i+1, n-1):
          
            for k in range(j+1, n):
              
                if (arr[i] + arr[j] + arr[k] == 0):
                    print(arr[i], arr[j], arr[k])
                    found = True
      
              
    # If no triplet with 0 sum 
    # found in array
    if (found == False):
        print(" not exist ")
  
# Driver code
arr = [0, -1, 2, -3, 1]
n = len(arr)
findTriplets(arr, n)
  
# This code is contributed by Smitha Dinesh Semwal    

0 -1 1
2 -3 1

Análisis de Complejidad: 

• Complejidad Temporal: O(n ³ ). 
  Como se requieren tres bucles anidados, la complejidad del tiempo es O(n ³ ).
• Espacio Auxiliar: O(1). 
  Dado que no se requiere espacio adicional, la complejidad del espacio es constante.

 
Método 2: El segundo método utiliza el proceso de Hashing para llegar al resultado y se resuelve en un tiempo menor de O(n ² ). 

Enfoque: Esto implica atravesar la array. Para cada elemento arr[i], encuentre un par con suma “-arr[i]”. Este problema se reduce a la suma de pares y se puede resolver en tiempo O(n) usando hashing.

Algoritmo: 

1. Cree un hashmap para almacenar un par clave-valor.
2. Ejecute un bucle anidado con dos bucles, el bucle exterior de 0 a n-2 y el bucle interior de i+1 a n-1
3. Compruebe si la suma de los elementos i-ésimo y j-ésimo multiplicada por -1 está presente en el mapa hash o no
4. Si el elemento está presente en el hashmap, imprima el triplete; de ​​lo contrario, inserte el elemento j en el hashmap.

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

# Python3 program to find triplets 
# in a given array whose sum is zero 
  
# function to print triplets with 0 sum 
def findTriplets(arr, n):
    found = False
    for i in range(n - 1):
  
        # Find all pairs with sum 
        # equals to "-arr[i]" 
        s = set()
        for j in range(i + 1, n):
            x = -(arr[i] + arr[j])
            if x in s:
                print(x, arr[i], arr[j])
                found = True
            else:
                s.add(arr[j])
    if found == False:
        print("No Triplet Found")
  
# Driver Code
arr = [0, -1, 2, -3, 1]
n = len(arr)
findTriplets(arr, n)
  
# This code is contributed by Shrikant13

-1 0 1
-3 2 1

Análisis de Complejidad: 

• Complejidad Temporal: O(n ² ). 
  Dado que se requieren dos bucles anidados, la complejidad del tiempo es O(n ² ).
• Espacio Auxiliar: O(n). 
  Dado que se requiere un hashmap, la complejidad del espacio es lineal.

 
Método 3: Este método usa Ordenar para llegar al resultado correcto y se resuelve en tiempo O(n ² ). 
 

Enfoque: El método anterior requiere espacio adicional. La idea se basa en el método 2 de esta publicación. Para cada elemento verifica que haya un par cuya suma sea igual al valor negativo de ese elemento.

Algoritmo: 

1. Ordene la array en orden ascendente.
2. Atraviesa la array de principio a fin.
3. Para cada índice i , cree dos variables l = i + 1 y r = n – 1
4. Ejecute un bucle hasta que l sea menor que r si la suma de array[i], array[l] y array[r] es igual a cero, luego imprima el triplete y rompa el bucle
5. Si la suma es menor que cero, aumente el valor de l, al aumentar el valor de l, la suma aumentará a medida que se ordene la array, por lo que array [l + 1]> array [l]
6. Si la suma es mayor que cero, disminuya el valor de r, al aumentar el valor de l, la suma disminuirá a medida que se ordene la array, por lo que array[r-1] < array [r] .

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

# python program to find triplets in a given
# array whose sum is zero
  
# function to print triplets with 0 sum
def findTriplets(arr, n):
  
    found = False
  
    # sort array elements
    arr.sort()
  
    for i in range(0, n-1):
      
        # initialize left and right
        l = i + 1
        r = n - 1
        x = arr[i]
        while (l < r):
          
            if (x + arr[l] + arr[r] == 0):
                # print elements if it's sum is zero
                print(x, arr[l], arr[r])
                l+=1
                r-=1
                found = True
              
  
            # If sum of three elements is less
            # than zero then increment in left
            elif (x + arr[l] + arr[r] < 0):
                l+=1
  
            # if sum is greater than zero than
            # decrement in right side
            else:
                r-=1
          
    if (found == False):
        print(" No Triplet Found")
  
  
# Driven source
arr = [0, -1, 2, -3, 1]
n = len(arr)
findTriplets(arr, n)
  
# This code is contributed by Smitha Dinesh Semwal

-3 1 2
-1 0 1

Análisis de Complejidad: 

• Complejidad del Tiempo : O(n ² ). 
  Solo se requieren dos bucles anidados, por lo que la complejidad del tiempo es O(n ² ).
• Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que la complejidad del tiempo es constante.

Consulte el artículo completo sobre Buscar todos los trillizos con suma cero para obtener más detalles.