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 de prefixos 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?

Tempo O(n) com um total acumulado da esquerda para a direita e espaço extra O(1) , além da resposta. Recalcular cada prefixo desde o início é O(n²) .

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

Sim. Percorra do índice 1 até o fim e defina nums[i] += nums[i-1] . Nesse momento, nums[i-1] já contém o total de tudo até ele, então cada elemento termina como sua soma de prefixos. Você perde os valores originais.

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

A soma de um trecho nums[l..r] é prefix[r] - prefix[l-1] , ou prefix[r] quando l = 0 . Com [3, 4, 8, 9, 14] , os índices de 2 a 4 somam 14 - 4 = 10 . Cada consulta leva O(1) após uma passagem de 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 é nums[0] + nums[1] + ... + nums[i], a soma dos primeiros i+1 números.

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 de 32 bits com sinal.

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 diminuem 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 total acumulado, que é ele mesmo, então a resposta é [7].

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 do 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 prefixos vizinhos diferem por um elemento. Recalcular cada prefixo desde o início repete quase todo o trabalho. Em vez disso, mantenha um total acumulado e cada resposta exige uma única adição.

Some cada prefixo desde o início

Intuição

Siga a definição: para cada índice i, comece um total em 0, some nums[0] até nums[i] e armazene-o. Isso está correto porque cada resposta é calculada exatamente como definido.

O índice i custa i+1 adições, então o array custa n(n+1)/2: cerca de 1.25 × 10^7 adições para n = 5000, em que 5000 seria suficiente.

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

Manter um total acumulado

Intuição

A soma dos primeiros i+1 números é a soma dos primeiros i mais nums[i]: result[i] = result[i-1] + nums[i]. Assim, você nunca precisa voltar mais de um passo, e uma variável total é suficiente. Para [3, 1, 4, 1, 5], os valores são 3, 4, 8, 9, 14, que é a resposta.

Cada elemento exige uma adição: tempo O(n) e espaço extra O(1), além da resposta.

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.
Escreva 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

Redefinir total dentro do loop. Cada resposta se torna apenas nums[i], e [3, 1, 4] volta sem alterações.
Ler result[i-1] em i = 0. Na maioria das linguagens, isso acessa uma posição fora dos limites; Python lê o último elemento, então uma versão in-place soma o último número ao primeiro.
Interromper o loop interno da força bruta em j < i. Isso deixa nums[i] de fora, então cada resposta fica com um número a menos.
Em R, aumentar a resposta com result <- c(result, total) copia o vetor a cada etapa e torna a abordagem rápida quadrática. Aloque o tamanho total primeiro.
Em C, esquecer *returnSize = numsSize. Assim, quem chamou 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 de prefixos 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?

Tempo O(n) com um total acumulado da esquerda para a direita e espaço extra O(1), além da resposta. Recalcular cada prefixo desde o início é O(n²).

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

Sim. Percorra do índice 1 até o fim e defina nums[i] += nums[i-1]. Nesse momento, nums[i-1] já contém o total de tudo até ele, então cada elemento termina como sua soma de prefixos. Você perde os valores originais.

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

A soma de um trecho nums[l..r] é prefix[r] - prefix[l-1], ou prefix[r] quando l = 0. Com [3, 4, 8, 9, 14], os índices de 2 a 4 somam 14 - 4 = 10. Cada consulta leva O(1) após uma passagem de O(n).

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

Teste #1

Teste #2

Teste #3

Argumento

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

Saída Esperada

[3, 4, 8, 9, 14]