Running Sum of an Array

Q: Qu’est-ce que la somme cumulée d’un tableau ?

C'est un deuxième tableau où chaque élément est le total de tous les éléments jusqu'à la position correspondante incluse dans le premier tableau. On l'appelle aussi somme préfixe ou somme cumulée. La somme cumulée de [3, 1, 4, 1, 5] est [3, 4, 8, 9, 14] .

Q: Quelle est la complexité temporelle du calcul d’une somme cumulée ?

Temps O(n) avec un total cumulé de gauche à droite, et espace supplémentaire O(1) en plus de la réponse. Recalculer chaque préfixe depuis le début prend O(n²) .

Q: Peux-tu calculer la somme cumulée sur place ?

Oui. Parcourez le tableau de l’indice 1 jusqu’à la fin et définissez nums[i] += nums[i-1] . À ce stade, nums[i-1] contient déjà le total de tous les éléments jusqu’à cet indice, donc chaque élément finit par contenir sa somme préfixe. Vous perdez les valeurs d’origine.

Q: Comment les sommes préfixes aident-elles à répondre aux requêtes de somme sur une plage ?

La somme d’une tranche nums[l..r] est prefix[r] - prefix[l-1] , ou prefix[r] lorsque l = 0 . Avec [3, 4, 8, 9, 14] , les indices 2 à 4 totalisent 14 - 4 = 10 . Chaque requête prend O(1) après un passage de O(n) .

DébutantSommes préfixes

+10

Vous obtenez un tableau d’entiers nums. Retournez un nouveau tableau de même longueur dont l’élément à l’index i est nums[0] + nums[1] + ... + nums[i], la somme des i+1 premiers nombres.

Fonction

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

numsinteger-array: les nombres à additionner de gauche à droite
Renvoieinteger-array: les totaux cumulés, un pour chaque élément de nums

Contraintes

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
Chaque total cumulé tient dans un entier signé de 32 bits.

Exemples

Entrée: nums = [3, 1, 4, 1, 5]
Sortie: [3, 4, 8, 9, 14]
Explication: Continuez à additionner : 3, puis 3 + 1 = 4, 4 + 4 = 8, 8 + 1 = 9 et 9 + 5 = 14. Chaque total est placé à l’indice du dernier nombre ajouté.

Entrée: nums = [-2, 5, -3]
Sortie: [-2, 3, 0]
Explication: Les nombres négatifs font baisser le total : -2, puis -2 + 5 = 3, puis 3 + (-3) = 0.

Entrée: nums = [7]
Sortie: [7]
Explication: Un seul nombre a un total cumulé égal à lui-même, donc la réponse est [7].

Pour aller plus loin

Peux-tu créer la même chose pour une grille, où chaque cellule contient le total du rectangle allant du coin supérieur gauche jusqu’à cette cellule ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Chaque réponse est la somme d’un préfixe de nums, et deux préfixes voisins diffèrent d’un seul élément. Recalculer chaque préfixe depuis le début répète presque tout le travail. Conserve plutôt un total d’une étape à l’autre : chaque réponse ne nécessite alors qu’une seule addition.

Additionnez chaque préfixe depuis le début

Intuition

Suivez la définition : pour chaque indice i, initialisez un total à 0, ajoutez nums[0] jusqu’à nums[i], puis stockez-le. C’est correct, car chaque réponse est calculée exactement comme défini.

L’indice i nécessite i+1 additions, donc le tableau en nécessite n(n+1)/2 : environ 1.25 × 10^7 additions pour n = 5000, ce qui devrait convenir pour 5000.

Algorithme

Créez un tableau de réponses de longueur n.
Pour chaque indice i, définissez total = 0.
Ajoutez nums[j] à total pour chaque j de 0 à i.
Stockez total à l’indice i du tableau de réponses, et renvoyez le tableau de réponses après le dernier indice.

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

Garder un total cumulatif

Intuition

La somme des i+1 premiers nombres est la somme des i premiers à laquelle on ajoute nums[i] : result[i] = result[i-1] + nums[i]. On ne revient donc jamais plus d’un pas en arrière, et une seule variable total suffit. Pour [3, 1, 4, 1, 5], on obtient 3, 4, 8, 9, 14, ce qui est la réponse.

Chaque élément nécessite une addition : un temps en O(n) et un espace supplémentaire en O(1), en plus de la réponse.

Algorithme

Créez un tableau de réponses de longueur n et définissez total = 0.
Parcourez les indices de gauche à droite et ajoutez nums[i] à total.
Écrivez total à l’indice i du tableau de réponses.
Renvoyez le tableau de réponses.

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

Pièges et cas limites

Réinitialiser total dans la boucle. Chaque réponse devient uniquement nums[i], et [3, 1, 4] revient inchangé.
Lire result[i-1] à i = 0. La plupart des langages dépassent les limites ; Python lit le dernier élément, donc une version en place ajoute le dernier nombre au premier.
Arrêter la boucle interne de la méthode par force brute à j < i. Cela exclut nums[i], donc chaque réponse comporte un nombre de moins.
En R, faire croître le résultat avec result <- c(result, total) copie le vecteur à chaque étape et rend l’approche rapide quadratique. Allouez d’abord la longueur totale.
En C, oublier *returnSize = numsSize. L’appelant ne sait alors pas combien de totaux lire.

Questions fréquentes4

Qu’est-ce que la somme cumulée d’un tableau ?

C'est un deuxième tableau où chaque élément est le total de tous les éléments jusqu'à la position correspondante incluse dans le premier tableau. On l'appelle aussi somme préfixe ou somme cumulée. La somme cumulée de [3, 1, 4, 1, 5] est [3, 4, 8, 9, 14].

Quelle est la complexité temporelle du calcul d’une somme cumulée ?

Temps O(n) avec un total cumulé de gauche à droite, et espace supplémentaire O(1) en plus de la réponse. Recalculer chaque préfixe depuis le début prend O(n²).

Peux-tu calculer la somme cumulée sur place ?

Oui. Parcourez le tableau de l’indice 1 jusqu’à la fin et définissez nums[i] += nums[i-1]. À ce stade, nums[i-1] contient déjà le total de tous les éléments jusqu’à cet indice, donc chaque élément finit par contenir sa somme préfixe. Vous perdez les valeurs d’origine.

Comment les sommes préfixes aident-elles à répondre aux requêtes de somme sur une plage ?

La somme d’une tranche nums[l..r] est prefix[r] - prefix[l-1], ou prefix[r] lorsque l = 0. Avec [3, 4, 8, 9, 14], les indices 2 à 4 totalisent 14 - 4 = 10. Chaque requête prend O(1) après un passage de O(n).

def runningSum(nums):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Argument

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

Résultat attendu

[3, 4, 8, 9, 14]