Programa Javascript para encontrar todos los trillizos 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: 

<script>
// A simple Javascript program to find
//three elements whose sum is equal to zero
    arr = [0, -1, 2, -3, 1];
      
// Prints all triplets in arr[] with 0 sum    
    function findTriplets(arr) {
        let found = false;
        for (let i = 0; i < arr.length - 2; i++) {
        for (let j = i + 1; j < arr.length - 1; j++) {
            for (let k = j + 1; k < arr.length; k++) {
                if (arr[i] + arr[j] + arr[k] === 0)
                {
                    document.write(arr[i]);
                    document.write(" ");
                    document.write(arr[j]);
                    document.write(" ");
                    document.write(arr[k]);
                    document.write("<br>");
                    found = true;
                     
                }
            }
        }
        // If no triplet with 0 sum found in array
        if(found === false) {
            document.write(" not exist ");
        }
    }
   }
    findTriplets(arr);
// This code is contributed by Surbhi Tyagi
</script>

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: 

<script>
   
// Javascript program to find triplets in a given
// array whose sum is zero
  
// function to print triplets with 0 sum
function findTriplets(arr, n)
{
    var found = false;
  
    for (var i = 0; i < n - 1; i++)
    {
        // Find all pairs with sum equals to
        // "-arr[i]"
        var s = new Set();
        for (var j = i + 1; j < n; j++)
        {
            var x = -(arr[i] + arr[j]);
            if (s.has(x))
            {
                document.write( x + " " + arr[i] + " " + arr[j] + "<br>");
                found = true;
            }
            else
                s.add(arr[j]);
        }
    }
  
    if (found == false)
        document.write( " No Triplet Found" );
}
  
// Driver code
var arr = [0, -1, 2, -3, 1];
var n = arr.length;
findTriplets(arr, n);
  
// This code is contributed by famously.
</script>

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

<script>
  
// Javascript program to find triplets in a given
// array whose sum is zero
  
// function to print triplets with 0 sum
function findTriplets(arr, n)
{
    let found = false;
  
    // sort array elements
    arr.sort((a, b) => a - b);
  
    for (let i=0; i<n-1; i++)
    {
        // initialize left and right
        let l = i + 1;
        let r = n - 1;
        let x = arr[i];
        while (l < r)
        {
            if (x + arr[l] + arr[r] == 0)
            {
                // print elements if it's sum is zero
                document.write(x + " ");
                document.write(arr[l]+ " ");
                document.write(arr[r]+ " " + "<br>");
                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)
        document.write(" No Triplet Found" + "<br>");
}
  
// Driven source
  
    let arr = [0, -1, 2, -3, 1];
    let n = arr.length;
    findTriplets(arr, n);
  
  
// This code is contributed by Mayank Tyagi
  
</script>

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