Programa Javascript para encontrar si hay un subarreglo con 0 suma

Dada una array de números positivos y negativos, encuentre si hay una subarreglo (de tamaño al menos uno) con suma 0.

Ejemplos: 

Entrada: {4, 2, -3, 1, 6}
Salida: verdadero 
Explicación:
Hay un subarreglo con suma cero del índice 1 al 3.

Entrada: {4, 2, 0, 1, 6}
Salida : verdadero 
Explicación:
Hay un subarreglo con suma cero del índice 2 al 2.

Entrada: {-3, 2, 3, 1, 6}
Salida: falso

Una solución simple es considerar todos los subarreglos uno por uno y verificar la suma de cada subarreglo. Podemos ejecutar dos bucles: el bucle exterior elige un punto de inicio i y el bucle interior prueba todos los subarreglos a partir de i (ver esto para la implementación). La complejidad temporal de este método es O(n 2 ).
También podemos usar hash . La idea es iterar a través de la array y para cada elemento arr[i], calcular la suma de los elementos de 0 a i (esto se puede hacer simplemente como sum += arr[i]). Si la suma actual se ha visto antes, entonces hay una array de suma cero. Hashing se utiliza para almacenar los valores de la suma para que podamos almacenar rápidamente la suma y averiguar si la suma actual se ve antes o no.
Ejemplo :

arr[] = {1, 4, -2, -2, 5, -4, 3}

If we consider all prefix sums, we can
notice that there is a subarray with 0
sum when :
1) Either a prefix sum repeats or
2) Or prefix sum becomes 0.

Prefix sums for above array are:
1, 5, 3, 1, 6, 2, 5

Since prefix sum 1 repeats, we have a subarray
with 0 sum. 

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

Javascript

// A Javascript program to
//  find if there is a zero sum subarray
  
const subArrayExists = (arr) => {
    const sumSet = new Set();
  
    // Traverse through array 
    // and store prefix sums
    let sum = 0;
    for (let i = 0 ; i < arr.length ; i++)
    {
        sum += arr[i];
  
        // If prefix sum is 0 
        // or it is already present
        if (sum === 0 || sumSet.has(sum))
            return true;
  
        sumSet.add(sum);
    }
    return false;
}
  
// Driver code
  
const arr =  [-3, 2, 3, 1, 6];
if (subArrayExists(arr))
    console.log("Found a subarray with 0 sum");
else
    console.log("No Such Sub Array Exists!");
Producción

No Such Sub Array Exists!

La complejidad temporal de esta solución se puede considerar como O(n) bajo el supuesto de que tenemos una buena función hash que permite operaciones de inserción y recuperación en tiempo O(1). 
Complejidad espacial : O (n). Aquí requerimos espacio adicional para unordered_set para insertar elementos de array.
 

Consulte el artículo completo sobre Buscar si hay un subarreglo con suma 0 para obtener más detalles.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *