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!");
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