Running Sum of an Array
Recibes un array de enteros nums. Devuelve un nuevo array de la misma longitud cuyo elemento en el índice i es nums[0] + nums[1] + ... + nums[i], el total de los primeros i+1 números.
Función
- 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-104 ≤ nums[i] ≤ 104- Cada suma acumulada 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és3 + 1 = 4,4 + 4 = 8,8 + 1 = 9y9 + 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 que el total disminuya:
-2, después-2 + 5 = 3, después3 + (-3) = 0.
- Entrada
- nums = [7]
- Salida
- [7]
- Explicación
- Un solo número tiene un total acumulado, él mismo, así que la respuesta es
[7].
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.
¿Cómo se relaciona la respuesta en el índice
icon la respuesta en el índicei-1?Las dos sumas difieren exactamente en un número,
nums[i]. Nunca necesitas volver a sumar un prefijo desde el principio.Mantén una variable
total. Recorrenumsde izquierda a derecha, suma cada número atotaly escribetotalen la respuesta en el mismo índice.
Solución
Cada respuesta es la suma de un prefijo de nums, y los prefijos consecutivos difieren en un elemento. Volver a calcular cada prefijo desde el principio repite casi todo el trabajo. En su lugar, mantén un total acumulado y cada respuesta requerirá una sola suma.
Suma cada prefijo desde cero
Intuición
Sigue la definición: para cada índice i, empieza un total en 0, suma nums[0] hasta nums[i] y guárdalo. Es correcto porque cada respuesta se calcula exactamente como se define.
El índice i requiere i+1 sumas, así que el arreglo requiere n(n+1)/2: aproximadamente 1.25 × 10^7 sumas para n = 5000, donde 5000 bastaría.
Algoritmo
- Crea un array de respuestas de longitud
n. - Para cada índice
i, establecetotal = 0. - Suma
nums[j]atotalpor cadajdesde0hastai. - Almacena
totalen el índiceide 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 resultCalcula un total acumulado
Intuición
La suma de los primeros i+1 números es la suma de los primeros i más nums[i]: result[i] = result[i-1] + nums[i]. Así que nunca tienes que retroceder más de un paso, y basta con una variable total. Para [3, 1, 4, 1, 5] da 3, 4, 8, 9, 14, que es la respuesta.
Cada elemento requiere una suma: tiempo O(n) y espacio extra O(1), además de la respuesta.
Algoritmo
- Crea un arreglo de respuestas de longitud
ny establecetotal = 0. - Recorre los índices de izquierda a derecha y suma
nums[i]atotal. - Escribe
totalen el índiceide 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
- Restablecer
totaldentro del bucle. Cada respuesta se convierte únicamente ennums[i], y[3, 1, 4]vuelve sin cambios. - Leer
result[i-1]cuandoi = 0. La mayoría de los lenguajes acceden a una posición fuera de los límites; Python lee el último elemento, por lo que una versión in situ suma el último número al primero. - Detener el bucle interno de fuerza bruta cuando
j < i. Omitenums[i], así que cada respuesta queda corta por un número. - En R, ampliar la respuesta con
result <- c(result, total)copia el vector en cada paso y hace que el enfoque rápido tenga una complejidad cuadrática. Asigna primero la longitud completa. - En C, olvidar
*returnSize = numsSize. Entonces, quien llama no sabe cuántos totales debe leer.
Preguntas frecuentes4
¿Cuál es la suma acumulada de un array?
Es un segundo arreglo en el que cada elemento es el total de todo hasta e incluyendo la misma posición en el primero. También se llama suma de prefijos o suma acumulativa. 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?
Tiempo O(n) con un total que se lleva de izquierda a derecha, y espacio extra O(1) aparte de la respuesta. Recalcular cada prefijo desde el principio 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]. Para entonces, nums[i-1] ya contiene el total de todo lo que hay hasta ese punto, así que cada elemento termina siendo su suma de prefijos. Pierdes los valores originales.
¿Cómo ayudan las sumas de prefijos con las consultas de suma de rangos?
El total de un segmento nums[l..r] es prefix[r] - prefix[l-1], o prefix[r] cuando l = 0. Con [3, 4, 8, 9, 14], los índices del 2 al 4 suman 14 - 4 = 10. Cada consulta tarda O(1) después de una pasada O(n).
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def runningSum(nums):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumento
nums = [3, 1, 4, 1, 5]
Salida Esperada
[3, 4, 8, 9, 14]