PUERTA | PUERTA-CS-2006 | Pregunta 54

Dadas dos arrays de números a ₁ , a ₂ , a ₃ ,…a _n y b ₁ , b ₂ , .. b _n donde cada número es 0 o 1, el algoritmo más rápido para encontrar el lapso más grande (i, j) tal que un _yo + un _yo+1 , ….un _j = segundo _yo + segundo _yo+1 , .. segundo _j . o informar que no existe tal lapso,
(A) Toma el tiempo O(n ³ ) y Ω(2 ⁿ ) si se permite el hashing
(B) Toma el tiempo O(n ³ ) y Ω(n ^2.5 ) en el modelo de comparación clave
(C) Toma θ(n) tiempo y espacio
(D) Toma O(√n) tiempo solo si la suma de los 2n elementos es un número par

Respuesta: (C)
Explicación: El problema se puede resolver en Toma θ(n ) tiempo y espacio.

La idea se basa en las siguientes observaciones.

1. Dado que hay un total de n elementos, la suma máxima es n para ambas arrays.
2. La diferencia entre dos sumas varía de -n a n . Entonces hay un total de 2n + 1 valores posibles de diferencia.
3. Si las diferencias entre las sumas de prefijos de dos arrays se vuelven iguales en dos puntos, entonces las subarreglas entre estos dos puntos tienen la misma suma.

A continuación se muestra el algoritmo completo.

1. Cree una array auxiliar de tamaño 2n+1 para almacenar los puntos de inicio de todos los valores posibles de las diferencias (tenga en cuenta que los valores posibles de las diferencias varían de -n a n, es decir, hay un total de 2n+1 valores posibles)
2. Inicialice los puntos de inicio de todas las diferencias como -1.
3. Inicialice maxLen como 0 y prefije las sumas de ambas arrays como 0, preSum1 = 0, preSum2 = 0
4. Atraviese ambas arrays desde i = 0 hasta n-1.
   1. Actualizar sumas de prefijos: preSum1 += arr1[i], preSum2 += arr2[i]
   2. Calcule la diferencia de las sumas de prefijos actuales: curr_diff = preSum1 – preSum2
   3. Encuentre el índice en la array diff: diffIndex = n + curr_diff // curr_diff puede ser negativo y puede ir hasta -n
   4. Si curr_diff es 0, entonces i+1 es maxLen hasta ahora
   5. De lo contrario, si curr_diff se ve por primera vez, es decir, el punto de inicio de la diferencia actual es -1, entonces actualice el punto de inicio como i
   6. De lo contrario ( curr_diff NO se ve por primera vez), luego considere i como punto final y encuentre la longitud del mismo intervalo de suma actual. Si esta longitud es mayor, actualice maxLen
5. Devolver maxLen

Consulte el intervalo más largo con la misma suma en dos arrays binarias para ver el código de ejecución completo
Cuestionario de esta pregunta