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 ?

Avec un total unique reporté de gauche à droite, cela prend un temps de O(n) , avec une addition par élément, et nécessite un espace supplémentaire de O(1) en plus de la réponse. Recalculer chaque préfixe depuis le début coûte n(n+1)/2 additions, soit 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] . Chaque élément contient alors sa somme préfixe, car nums[i-1] a déjà été transformé en la somme de tous les éléments qui le précèdent. Cela n’utilise aucun autre tableau que celui d’entrée, mais détruit les valeurs d’origine.

Q: Comment les sommes préfixes facilitent-elles les requêtes de somme sur une plage ?

Une fois les sommes cumulées calculées, le total de n’importe quelle tranche nums[l..r] est prefix[r] - prefix[l-1] , ou prefix[r] lorsque l = 0 . Avec les sommes cumulées [3, 4, 8, 9, 14] , les indices de 2 à 4 totalisent 14 - 4 = 10 . Chaque requête prend O(1) après un seul parcours en O(n) .

DébutantSommes préfixes

+10

Vous obtenez un tableau d’entiers nums. Renvoyez un nouveau tableau de même longueur dont l’élément à l’indice i est nums[0] + nums[1] + ... + nums[i], le total cumulé après avoir lu les i+1 premiers nombres en partant de la gauche.

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: Continue d’additionner : 3, puis 3 + 1 = 4, 4 + 4 = 8, 8 + 1 = 9 et 9 + 5 = 14. Chaque total est placé à l’index 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 seul total cumulé, lui-même ; la réponse est donc [7].

+13 tests cachés à la soumission

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 exactement. Recalculer chaque préfixe depuis le début répète presque tout le travail, tandis que conserver un total et le mettre à jour permet d’obtenir chaque réponse avec une seule addition. Le résultat est le tableau des sommes préfixes, l’outil qui permet de calculer rapidement des sommes sur des intervalles.

Additionner chaque préfixe depuis zéro

Intuition

Suivez la définition à la lettre. Pour chaque indice i, repartez d’un total égal à 0, ajoutez nums[0] à nums[i], puis stockez le résultat. Pour [3, 1, 4, 1, 5], la dernière réponse additionne les cinq nombres : 3 + 1 + 4 + 1 + 5 = 14.

C’est correct, mais cela répète les mêmes opérations. Le total pour l’indice 4 repart de nums[0], alors que le total pour l’indice 3, 9, contient déjà la somme des quatre premiers nombres. L’indice i nécessite i+1 additions, donc le tableau entier nécessite 1 + 2 + ... + n = n(n+1)/2 additions. Pour n = 5000, cela représente environ 1.25 × 10^7 additions, alors que 5000 suffiraient.

En dehors du tableau de résultats, que vous renvoyez de toute façon, il ne conserve qu’un total et deux indices, donc l’espace supplémentaire est O(1).

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, puis renvoyez le tableau 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

Tenir un total cumulé

Intuition

La somme des i+1 premiers nombres est la somme des i premiers nombres plus nums[i] : result[i] = result[i-1] + nums[i]. Tu ne reviens donc jamais en arrière de plus d’une étape. Garde une seule variable total, ajoute-y chaque nombre au fur et à mesure que tu le lis, puis écris la nouvelle valeur dans la réponse.

Pour [3, 1, 4, 1, 5], total prend les valeurs 3, 4, 8, 9, 14, et ces cinq valeurs constituent la réponse. Chaque élément est lu une fois et nécessite une addition, donc le temps d’exécution est de O(n). En plus du tableau de réponse, la seule mémoire utilisée est total, donc l’espace supplémentaire est de O(1).

Aucun total ici ne peut dépasser 5000 × 10^4 = 5 × 10^7, ce qui tient dans un entier de 32 bits. Avec des entrées plus grandes, les sommes préfixes sont un cas classique de débordement, et un total de 64 bits est le choix sûr par défaut.

Algorithme

Créez un tableau de réponses de longueur n et définissez total = 0.
Parcourez les index de gauche à droite et ajoutez nums[i] à total.
Écrivez total à l’index i du tableau de réponses.
Retournez 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

La boucle ne contient qu’une seule ligne de travail réelle ; les erreurs portent donc sur l’emplacement du total et sur sa destination.

Réinitialiser total à l’intérieur de la boucle. Chaque réponse devient uniquement nums[i], et [3, 1, 4] est renvoyé sans changement.
Utiliser result[i] = result[i-1] + nums[i] sans gérer i = 0. L’indice -1 est hors limites dans la plupart des langages ; en Python, il désigne le dernier élément. Une version en place qui commence à 0 ajoute donc le dernier nombre au premier.
Arrêter la boucle interne de la première approche à j < i. Cela exclut nums[i], et chaque réponse manque donc un nombre.
Faire croître la réponse en la recopiant. En R, result <- c(result, total) recopie le vecteur entier à chaque étape, ce qui rend de nouveau quadratique l’approche rapide. Allouez d’abord la longueur totale.
Oublier *returnSize = numsSize en C. Sans cela, l’appelant ne sait 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 ?

Avec un total unique reporté de gauche à droite, cela prend un temps de O(n), avec une addition par élément, et nécessite un espace supplémentaire de O(1) en plus de la réponse. Recalculer chaque préfixe depuis le début coûte n(n+1)/2 additions, soit 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]. Chaque élément contient alors sa somme préfixe, car nums[i-1] a déjà été transformé en la somme de tous les éléments qui le précèdent. Cela n’utilise aucun autre tableau que celui d’entrée, mais détruit les valeurs d’origine.

Comment les sommes préfixes facilitent-elles les requêtes de somme sur une plage ?

Une fois les sommes cumulées calculées, le total de n’importe quelle tranche nums[l..r] est prefix[r] - prefix[l-1], ou prefix[r] lorsque l = 0. Avec les sommes cumulées [3, 4, 8, 9, 14], les indices de 2 à 4 totalisent 14 - 4 = 10. Chaque requête prend O(1) après un seul parcours en O(n).

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

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

Attendu

[3, 4, 8, 9, 14]