Running Sum of an Array

Q: O que é a soma acumulada de um array?

É um segundo array em que cada elemento é o total de tudo até e incluindo a mesma posição no primeiro array. Também é chamado de soma prefixada ou soma acumulada. A soma acumulada de [3, 1, 4, 1, 5] é [3, 4, 8, 9, 14] .

Q: Qual é a complexidade de tempo de calcular uma soma acumulada?

Com um total acumulado da esquerda para a direita, o tempo é O(n) , com uma adição por elemento, e o espaço extra é O(1) , além da resposta. Recalcular cada prefixo desde o início custa n(n+1)/2 adições, o que é O(n²) .

Q: Você consegue calcular a soma acumulada no próprio lugar?

Sim. Percorra do índice 1 até o final e defina nums[i] += nums[i-1] . Cada elemento então contém sua soma de prefixo, porque nums[i-1] já foi transformado no total de tudo o que vem antes dele. Isso não usa nenhum outro array além da entrada, mas destrói os valores originais.

Q: Como as somas de prefixo ajudam nas consultas de soma em intervalos?

Depois de obter as somas acumuladas, o total de qualquer intervalo nums[l..r] é prefix[r] - prefix[l-1] , ou prefix[r] quando l = 0 . Com as somas acumuladas [3, 4, 8, 9, 14] , os índices de 2 a 4 somam 14 - 4 = 10 . Cada consulta leva O(1) tempo após uma única passagem O(n) .

InicianteSoma de prefixos

+10

Você recebe um array de números inteiros nums. Retorne um novo array do mesmo tamanho cujo elemento no índice i seja nums[0] + nums[1] + ... + nums[i], o total acumulado após ler os primeiros i+1 números da esquerda para a direita.

Função

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

numsinteger-array: os números a serem somados da esquerda para a direita
Retornainteger-array: os totais acumulados, um para cada elemento de nums

Restrições

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
Todos os totais acumulados cabem em um inteiro com sinal de 32 bits.

Exemplos

Entrada: nums = [3, 1, 4, 1, 5]
Saída: [3, 4, 8, 9, 14]
Explicação: Continue somando: 3, depois 3 + 1 = 4, 4 + 4 = 8, 8 + 1 = 9 e 9 + 5 = 14. Cada total vai para o índice do último número adicionado.

Entrada: nums = [-2, 5, -3]
Saída: [-2, 3, 0]
Explicação: Números negativos reduzem o total: -2, depois -2 + 5 = 3, depois 3 + (-3) = 0.

Entrada: nums = [7]
Saída: [7]
Explicação: Um único número tem um único total acumulado, que é ele mesmo, então a resposta é [7].

+13 testes ocultos ao enviar

Para ir além

Você consegue criar a mesma coisa para uma grade, em que cada célula contém o total do retângulo desde o canto superior esquerdo até essa célula?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Cada resposta é a soma de um prefixo de nums, e dois prefixos consecutivos diferem por exatamente um elemento. Recalcular cada prefixo desde o início repete quase todo o trabalho, enquanto manter um total acumulado fornece cada resposta com uma única adição. O resultado é o array de soma de prefixos, a ferramenta por trás das somas rápidas de intervalos.

Some cada prefixo desde o início

Intuição

Siga a definição à risca. Para cada índice i, comece um novo total em 0, some nums[0] até nums[i] e armazene o resultado. Para [3, 1, 4, 1, 5], a última resposta soma os cinco números: 3 + 1 + 4 + 1 + 5 = 14.

Está correto, mas repete o trabalho. O total para o índice 4 começa novamente em nums[0], embora o total para o índice 3, 9, já contenha a soma dos quatro primeiros números. O índice i exige i+1 adições, então o array inteiro exige 1 + 2 + ... + n = n(n+1)/2. Para n = 5000, isso dá cerca de 1.25 × 10^7 adições, quando 5000 seriam suficientes.

Além do array de respostas, que você retorna de qualquer forma, ele mantém apenas um total e dois índices, então o espaço extra é O(1).

Algoritmo

Crie um array de respostas com comprimento n.
Para cada índice i, defina total = 0.
Adicione nums[j] a total para cada j de 0 a i.
Armazene total no índice i da resposta e retorne a resposta após o ú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

Mantenha um total acumulado

Intuição

A soma dos primeiros i+1 números é a soma dos primeiros i números mais nums[i]: result[i] = result[i-1] + nums[i]. Portanto, você nunca precisa voltar mais de uma etapa. Mantenha uma única variável total, some cada número a ela à medida que o lê e escreva o novo valor na resposta.

Para [3, 1, 4, 1, 5], total assume os valores 3, 4, 8, 9, 14, e esses cinco valores são a resposta. Cada elemento é lido uma vez e requer uma adição, então o tempo é O(n). Além do array de resposta, a única memória usada é total, então o espaço extra é O(1).

Nenhum total aqui pode ultrapassar 5000 × 10^4 = 5 × 10^7, o que cabe em um inteiro de 32 bits. Com entradas maiores, somas de prefixos são um caso clássico de overflow, e um total de 64 bits é a opção segura por padrão.

Algoritmo

Crie um array de respostas com comprimento n e defina total = 0.
Percorra os índices da esquerda para a direita e adicione nums[i] a total.
Grave total no índice i da resposta.
Retorne a resposta.

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

Armadilhas e casos extremos

O loop tem uma linha de trabalho real, então os erros dizem respeito a onde o total fica e para onde vai.

Redefinir total dentro do loop. Cada resposta se torna apenas nums[i], e [3, 1, 4] retorna sem alterações.
Usar result[i] = result[i-1] + nums[i] sem tratar i = 0. O índice -1 fica fora dos limites na maioria das linguagens e, em Python, é o último elemento; portanto, uma versão que modifica o array original e começa em 0 soma o último número ao primeiro.
Encerrar o loop interno da primeira abordagem em j < i. Isso deixa nums[i] de fora, então cada resposta fica um número abaixo do esperado.
Aumentar a resposta copiando. Em R, result <- c(result, total) copia o vetor inteiro a cada etapa, o que torna a abordagem rápida quadrática novamente. Aloque primeiro o comprimento total.
Esquecer *returnSize = numsSize em C. Sem isso, quem chamou a função não sabe quantos totais deve ler.

Perguntas frequentes4

O que é a soma acumulada de um array?

É um segundo array em que cada elemento é o total de tudo até e incluindo a mesma posição no primeiro array. Também é chamado de soma prefixada ou soma acumulada. A soma acumulada de [3, 1, 4, 1, 5] é [3, 4, 8, 9, 14].

Qual é a complexidade de tempo de calcular uma soma acumulada?

Com um total acumulado da esquerda para a direita, o tempo é O(n), com uma adição por elemento, e o espaço extra é O(1), além da resposta. Recalcular cada prefixo desde o início custa n(n+1)/2 adições, o que é O(n²).

Você consegue calcular a soma acumulada no próprio lugar?

Sim. Percorra do índice 1 até o final e defina nums[i] += nums[i-1]. Cada elemento então contém sua soma de prefixo, porque nums[i-1] já foi transformado no total de tudo o que vem antes dele. Isso não usa nenhum outro array além da entrada, mas destrói os valores originais.

Como as somas de prefixo ajudam nas consultas de soma em intervalos?

Depois de obter as somas acumuladas, o total de qualquer intervalo nums[l..r] é prefix[r] - prefix[l-1], ou prefix[r] quando l = 0. Com as somas acumuladas [3, 4, 8, 9, 14], os índices de 2 a 4 somam 14 - 4 = 10. Cada consulta leva O(1) tempo após uma única passagem O(n).

Python

def runningSum(nums):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado

[3, 4, 8, 9, 14]