Programa Java 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 Java program to find three elements
// whose sum is equal to zero
class num{
// Prints all triplets in arr[] with 0 sum
static void findTriplets(int[] arr, int n)
{
    boolean found = false;
    for (int i=0; i<n-2; i++)
    {
        for (int j=i+1; j<n-1; j++)
        {
            for (int k=j+1; k<n; k++)
            {
                if (arr[i]+arr[j]+arr[k] == 0)
                {
                    System.out.print(arr[i]);
                    System.out.print(" ");
                    System.out.print(arr[j]);
                    System.out.print(" ");
                    System.out.print(arr[k]);
                    System.out.print("
");
                    found = true;
                }
            }
        }
    }
  
    // If no triplet with 0 sum found in array
    if (found == false)
        System.out.println(" not exist ");
  
}
  
// Driver code
public static void main(String[] args)
{
    int arr[] = {0, -1, 2, -3, 1};
    int n =arr.length;
    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: 

// Java program to find triplets in a given
// array whose sum is zero
import java.util.*;
  
class GFG 
{
  
    // function to print triplets with 0 sum
    static void findTriplets(int arr[], int n) 
    {
        boolean found = false;
  
        for (int i = 0; i < n - 1; i++) 
        {
            // Find all pairs with sum equals to
            // "-arr[i]"
            HashSet<Integer> s = new HashSet<Integer>();
            for (int j = i + 1; j < n; j++) 
            {
                int x = -(arr[i] + arr[j]);
                if (s.contains(x)) 
                {
                    System.out.printf("%d %d %d
", x, arr[i], arr[j]);
                    found = true;
                } 
                else 
                {
                    s.add(arr[j]);
                }
            }
        }
  
        if (found == false)
        {
            System.out.printf(" No Triplet Found
");
        }
    }
  
    // Driver code
    public static void main(String[] args) 
    {
        int arr[] = {0, -1, 2, -3, 1};
        int n = arr.length;
        findTriplets(arr, n);
    }
}
  
// This code contributed by Rajput-Ji

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

// Java  program to find triplets in a given
// array whose sum is zero
import java.util.Arrays; 
import java.io.*;
  
class GFG {
    // function to print triplets with 0 sum
static void findTriplets(int arr[], int n)
{
    boolean found = false;
  
    // sort array elements
    Arrays.sort(arr);
  
    for (int i=0; i<n-1; i++)
    {
        // initialize left and right
        int l = i + 1;
        int r = n - 1;
        int x = arr[i];
        while (l < r)
        {
            if (x + arr[l] + arr[r] == 0)
            {
                // print elements if it's sum is zero
                    System.out.print(x + " ");
                    System.out.print(arr[l]+ " ");
                    System.out.println(arr[r]+ " ");
      
                l++;
                r--;
                found = true;
            }
  
            // If sum of three elements is less
            // than zero then increment in left
            else if (x + arr[l] + arr[r] < 0)
                l++;
  
            // if sum is greater than zero than
            // decrement in right side
            else
                r--;
        }
    }
  
    if (found == false)
            System.out.println(" No Triplet Found");
}
  
// Driven source
    public static void main (String[] args) {
  
    int arr[] = {0, -1, 2, -3, 1};
    int n =arr.length;
    findTriplets(arr, n);
    }
//This code is contributed by Tushil..    
}

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