Programa C++ 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 C++ program to find three elements// whose sum is equal to zero#includeusing namespace std;// Prints all triplets in arr[] with 0 sumvoid findTriplets(int arr[], int n){bool found = false;for (int i=0; iOutput0 -1 1
2 -3 1

C++

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