Running Sum of an Array

Q: ¿Cuál es la suma acumulada de un arreglo?

Es un segundo arreglo donde cada elemento es el total de todo hasta e incluida la misma posición en el primer arreglo. También se llama suma de prefijos o suma acumulada. La suma acumulada de [3, 1, 4, 1, 5] es [3, 4, 8, 9, 14] .

Q: ¿Cuál es la complejidad temporal de calcular una suma acumulada?

Con un total que se arrastra de izquierda a derecha, el tiempo es O(n) , una suma por elemento, y el espacio adicional, aparte de la respuesta, es O(1) . Recalcular cada prefijo desde el inicio cuesta n(n+1)/2 sumas, lo que es O(n²) .

Q: ¿Puedes calcular la suma acumulada en el mismo lugar?

Sí. Recorre desde el índice 1 hasta el final y establece nums[i] += nums[i-1] . Cada elemento contiene después su suma de prefijos, porque nums[i-1] ya se había convertido en el total de todo lo que había antes. Esto no usa ningún otro arreglo además del de entrada, pero destruye los valores originales.

Q: ¿Cómo ayudan las sumas de prefijos con las consultas de suma de rangos?

Una vez que tengas las sumas acumuladas, el total de cualquier segmento nums[l..r] es prefix[r] - prefix[l-1] , o prefix[r] cuando l = 0 . Con las sumas acumuladas [3, 4, 8, 9, 14] , los índices del 2 al 4 suman 14 - 4 = 10 . Cada consulta toma O(1) de tiempo después de una pasada de O(n) .

PrincipianteSuma de prefijos

+10

Recibes un arreglo de números enteros nums. Devuelve un nuevo arreglo de la misma longitud cuyo elemento en el índice i es nums[0] + nums[1] + ... + nums[i], el total acumulado después de leer los primeros i+1 números desde la izquierda.

Función

runningSum(nums: integer-array) → integer-array

numsinteger-array: los números que se deben sumar de izquierda a derecha
Devuelveinteger-array: los totales acumulados, uno por cada elemento de nums

Restricciones

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
Cada total acumulado cabe en un entero con signo de 32 bits.

Ejemplos

Entrada: nums = [3, 1, 4, 1, 5]
Salida: [3, 4, 8, 9, 14]
Explicación: Sigue sumando: 3, después 3 + 1 = 4, 4 + 4 = 8, 8 + 1 = 9 y 9 + 5 = 14. Cada total va al índice del último número sumado.

Entrada: nums = [-2, 5, -3]
Salida: [-2, 3, 0]
Explicación: Los números negativos hacen bajar el total: -2, después -2 + 5 = 3, después 3 + (-3) = 0.

Entrada: nums = [7]
Salida: [7]
Explicación: Un solo número tiene un único total acumulado, que es él mismo, así que la respuesta es [7].

+13 pruebas ocultas al enviar

Para ir más allá

¿Puedes construir lo mismo para una cuadrícula, donde cada celda contiene el total del rectángulo desde la esquina superior izquierda hasta esa celda?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Cada respuesta es la suma de un prefijo de nums, y dos prefijos vecinos difieren exactamente en un elemento. Recalcular cada prefijo desde el inicio repite casi todo el trabajo, mientras que mantener un total y actualizarlo permite obtener cada respuesta con una sola suma. El resultado es el arreglo de sumas de prefijos, la herramienta que permite calcular sumas de rangos rápidamente.

Suma cada prefijo desde cero

Intuición

Sigue la definición al pie de la letra. Para cada índice i, empieza un total nuevo en 0, suma nums[0] hasta nums[i] y guarda el resultado. Para [3, 1, 4, 1, 5], la última respuesta suma los cinco números: 3 + 1 + 4 + 1 + 5 = 14.

Es correcto, pero repite el trabajo. El total para el índice 4 vuelve a empezar desde nums[0], aunque el total del índice 3, 9, ya contiene la suma de los primeros cuatro números. El índice i requiere i+1 sumas, así que el arreglo completo requiere 1 + 2 + ... + n = n(n+1)/2. Para n = 5000, eso equivale a aproximadamente 1.25 × 10^7 sumas, cuando bastarían 5000.

Aparte del arreglo de respuestas, que de todos modos devuelves, solo mantiene un total y dos índices, así que el espacio adicional es O(1).

Algoritmo

Crea un arreglo de respuestas de longitud n.
Para cada índice i, establece total = 0.
Suma nums[j] a total para cada j desde 0 hasta i.
Almacena total en el índice i de la respuesta y devuelve la respuesta después del último índice.

def runningSum(nums):
    result = []
    for i in range(len(nums)):
        total = 0
        for j in range(i + 1):
            total += nums[j]
        result.append(total)
    return result

Lleva un total acumulado

Intuición

La suma de los primeros i+1 números es la suma de los primeros i números más nums[i]: result[i] = result[i-1] + nums[i]. Así que nunca retrocedes más de un paso. Mantén una sola variable total, súmale cada número a medida que lo lees y escribe el nuevo valor en la respuesta.

Para [3, 1, 4, 1, 5], total toma los valores 3, 4, 8, 9, 14, y esos cinco valores son la respuesta. Cada elemento se lee una vez y requiere una suma, así que el tiempo es O(n). Además del arreglo de respuestas, la única memoria utilizada es total, así que el espacio adicional es O(1).

Ningún total aquí puede superar 5000 × 10^4 = 5 × 10^7 de tamaño, lo que cabe en un entero de 32 bits. Con entradas más grandes, las sumas de prefijos son un caso clásico de desbordamiento, y un total de 64 bits es la opción segura predeterminada.

Algoritmo

Crea un arreglo de respuestas de longitud n y establece total = 0.
Recorre los índices de izquierda a derecha y suma nums[i] a total.
Escribe total en el índice i de la respuesta.
Devuelve la respuesta.

def runningSum(nums):
    result = []
    total = 0
    for num in nums:
        total += num
        result.append(total)
    return result

Errores comunes y casos límite

El bucle tiene una sola línea de trabajo real, así que los errores tienen que ver con dónde se encuentra el total y adónde va.

Restablecer total dentro del bucle. Cada respuesta se convierte únicamente en nums[i], y [3, 1, 4] vuelve sin cambios.
Usar result[i] = result[i-1] + nums[i] sin gestionar i = 0. El índice -1 está fuera de los límites en la mayoría de los lenguajes y, en Python, corresponde al último elemento, así que una versión in situ que empieza en 0 suma el último número al primero.
Detener el bucle interno del primer enfoque en j < i. Deja fuera nums[i], así que cada respuesta tiene un número menos.
Hacer crecer la respuesta copiando. En R, result <- c(result, total) copia todo el vector en cada paso, lo que vuelve a hacer cuadrático el enfoque rápido. Reserva primero el espacio para la longitud completa.
Olvidar *returnSize = numsSize en C. Sin esto, quien llama no sabe cuántos totales debe leer.

Preguntas frecuentes4

¿Cuál es la suma acumulada de un arreglo?

Es un segundo arreglo donde cada elemento es el total de todo hasta e incluida la misma posición en el primer arreglo. También se llama suma de prefijos o suma acumulada. La suma acumulada de [3, 1, 4, 1, 5] es [3, 4, 8, 9, 14].

¿Cuál es la complejidad temporal de calcular una suma acumulada?

Con un total que se arrastra de izquierda a derecha, el tiempo es O(n), una suma por elemento, y el espacio adicional, aparte de la respuesta, es O(1). Recalcular cada prefijo desde el inicio cuesta n(n+1)/2 sumas, lo que es O(n²).

¿Puedes calcular la suma acumulada en el mismo lugar?

Sí. Recorre desde el índice 1 hasta el final y establece nums[i] += nums[i-1]. Cada elemento contiene después su suma de prefijos, porque nums[i-1] ya se había convertido en el total de todo lo que había antes. Esto no usa ningún otro arreglo además del de entrada, pero destruye los valores originales.

¿Cómo ayudan las sumas de prefijos con las consultas de suma de rangos?

Una vez que tengas las sumas acumuladas, el total de cualquier segmento nums[l..r] es prefix[r] - prefix[l-1], o prefix[r] cuando l = 0. Con las sumas acumuladas [3, 4, 8, 9, 14], los índices del 2 al 4 suman 14 - 4 = 10. Cada consulta toma O(1) de tiempo después de una pasada de O(n).

Python

def runningSum(nums):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

nums = [3, 1, 4, 1, 5]

Esperado

[3, 4, 8, 9, 14]