Subarray Sum Equals K

+10

Vous obtenez un tableau d’entiers nums et un entier k. Comptez les sous-tableaux dont les éléments ont une somme exactement égale à k. Un sous-tableau est une suite d’un ou plusieurs éléments voisins. Deux sous-tableaux sont comptés séparément lorsqu’ils commencent ou se terminent à des positions différentes, même s’ils contiennent les mêmes valeurs. Les valeurs peuvent être négatives ou nulles.

Fonction

subarraySum(nums: integer-array, k: integer) → integer

numsinteger-array: le tableau d’entiers, qui peut contenir des valeurs négatives et des zéros
kinteger: la somme qu’un sous-tableau doit atteindre pour être comptabilisé
Renvoieinteger: le nombre de sous-tableaux dont la somme des éléments est égale à k

Contraintes

1 ≤ nums.length ≤ 2 × 10⁴
-1000 ≤ nums[i] ≤ 1000
-10⁷ ≤ k ≤ 10⁷
Un tableau de cette longueur comporte au plus 200,010,000 sous-tableaux, donc la réponse tient dans un entier signé de 32 bits.

Exemples

Entrée: nums = [3, 4, -7, 1, 3, 3, 1, -4]k = 7
Sortie: 4
Explication: Quatre séquences totalisent 7 : [3, 4], [1, 3, 3], [3, 3, 1] et [3, 4, -7, 1, 3, 3]. Dans la dernière, le -7 annule le 3 et le 4, et la somme remonte ensuite à 7 ; une séquence peut donc correspondre même après que sa somme a dépassé k.

Entrée: nums = [1, -1, 0]k = 0
Sortie: 3
Explication: Trois sous-tableaux ont une somme égale à 0 : [1, -1], [0] et le tableau entier [1, -1, 0]. La séquence [-1, 0] a une somme égale à -1, elle ne compte donc pas.

Entrée: nums = [2, 2, 2]k = 4
Sortie: 2
Explication: La séquence [2, 2] aux indices 0 et 1 et la séquence [2, 2] aux indices 1 et 2 contiennent les mêmes valeurs, mais se trouvent à des positions différentes, donc elles comptent toutes les deux. La somme de l’ensemble du tableau est égale à 6.

+17 tests cachés à la soumission

Pour aller plus loin

Comment modifierais-tu la solution pour qu’elle renvoie la longueur du sous-tableau le plus long dont la somme est égale à k, toujours en O(n) ?

Indices

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

0 sur 3 ouverts

Solution

Un tableau de n nombres comporte n(n+1)/2 sous-tableaux, soit environ 2 × 10^8 lorsque n = 2 × 10^4 : les additionner un par un est donc trop lent. Les valeurs négatives excluent également la fenêtre glissante : la somme d'une fenêtre peut diminuer puis augmenter à nouveau, donc aucune règle ne permet de savoir quand la réduire. L'idée qui permet de résoudre le problème consiste à exprimer chaque somme de sous-tableau comme la différence de deux sommes préfixes. Compter les sous-tableaux qui se terminent à l'élément actuel et dont la somme est égale à k revient alors à compter les sommes préfixes antérieures égales à la somme préfixe actuelle moins k, et une table de hachage permet de le faire en un seul passage.

Chaque début avec un total cumulé

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Chaque sous-tableau a un premier indice start et un dernier indice end. Si tu parcours chaque paire et vérifies sa somme, tu comptes chaque sous-tableau exactement une fois, donc le décompte est correct.

Tu n’as pas besoin d’une troisième boucle pour additionner les éléments de chaque sous-tableau. Fixe start, puis déplace end d’un pas vers la droite à la fois et ajoute nums[end] à un total cumulatif. Le total contient toujours la somme des éléments de start à end, donc chaque sous-tableau nécessite une addition et une comparaison.

Ne t’arrête pas lorsque le total atteint ou dépasse k. Une valeur négative ultérieure peut le faire redescendre : dans le premier exemple, le total à partir de l’indice 0 passe par 3, 7, 0, 1, 4, 7 ; ce départ a donc une deuxième correspondance à l’indice 5.

Le coût correspond au nombre de paires. Avec n = 2 × 10^4, il y en a environ 2 × 10^8, ce qui convient à C, mais est beaucoup trop lent pour Python, Ruby ou R.

Algorithme

Définissez count à 0.
Pour chaque start de 0 à n-1, définissez total à 0.
Pour chaque end de start à n-1, ajoutez nums[end] à total.
Si total est égal à k, ajoutez 1 à count, et continuez dans tous les cas.
Retournez count.

def subarraySum(nums, k):
    n = len(nums)
    count = 0
    for start in range(n):
        total = 0
        # Grow the subarray that begins at start, one element at a time
        for end in range(start, n):
            total += nums[end]
            if total == k:
                count += 1
    return count

Sommes préfixes avec une table de comptage

Intuition

Soit prefix[j] la somme des j premiers éléments, avec prefix[0] = 0 pour le préfixe vide. La somme du sous-tableau allant de l’indice i à l’indice j-1 est égale à prefix[j] - prefix[i]. Ainsi, un sous-tableau qui se termine à l’élément courant a une somme égale à k exactement lorsque la somme d’un préfixe antérieur est égale à la somme du préfixe courant moins k. Chaque préfixe antérieur de ce type indique le début d’un sous-tableau correspondant.

Parcours le tableau une seule fois. Garde la somme cumulée du préfixe et une table de hachage seen qui associe à chaque somme de préfixe le nombre de fois où elle est apparue. Pour chaque élément, ajoute d’abord seen[prefix - k] au compte, puis enregistre le préfixe courant. Effectuer la recherche avant l’enregistrement empêche qu’un sous-tableau soit vide : avec k = 0, enregistrer d’abord ferait correspondre le préfixe courant à lui-même.

Considère le premier exemple avec k = 7. Les sommes des préfixes sont 0, 3, 7, 0, 1, 4, 7, 8, 4. Lorsque le préfixe atteint 7 après l’indice 1, la table contient un 0, ce qui donne [3, 4]. Lorsqu’il atteint de nouveau 7 après l’indice 5, la table contient deux 0, le préfixe vide et le préfixe après le -7, qui donnent simultanément [3, 4, -7, 1, 3, 3] et [1, 3, 3]. À 8 après l’indice 6, la table contient un 1, ce qui donne [3, 3, 1]. Cela fait 4.

Initialiser la table avec un 0 déjà vu une fois permet de compter les sous-tableaux qui commencent à l’indice 0. Une table de comptage plutôt qu’un ensemble est importante, car une même somme de préfixe peut se répéter, et chaque occurrence commence un sous-tableau différent. Chaque élément nécessite une recherche et une mise à jour, donc le temps d’exécution est O(n), et la table contient au plus n+1 clés.

Algorithme

Créez une map seen avec seen[0] = 1, et définissez prefix et count à 0.
Pour chaque élément, ajoutez-le à prefix.
Ajoutez seen[prefix - k] à count, en considérant une clé manquante comme valant 0.
Ajoutez 1 à seen[prefix].
Retournez count.

def subarraySum(nums, k):
    # seen[p] = how many prefixes so far add up to p; the empty prefix adds up to 0
    seen = {0: 1}
    prefix = 0
    count = 0
    for num in nums:
        prefix += num
        # Each earlier prefix equal to prefix - k starts a subarray that ends here and sums to k
        count += seen.get(prefix - k, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

Pièges et cas limites

La plupart des mauvaises réponses viennent du fait de traiter l’entrée comme si toutes les valeurs étaient positives, ou de l’ordre des deux opérations sur la map.

Une fenêtre glissante qui se réduit dès que la somme dépasse k échoue avec des valeurs négatives. Sur le premier exemple, elle renvoie 2 au lieu de 4 : la fenêtre garde son bord gauche à l’index 0 jusqu’à ce que la somme dépasse 7 à l’index 6 ; elle n’essaie donc jamais [1, 3, 3] ni [3, 3, 1].
Omettre seen[0] = 1 fait manquer tous les sous-tableaux qui commencent à l’index 0. Pour nums = [5] et k = 5, le résultat est 0 au lieu de 1.
Enregistrer le préfixe courant avant la recherche compte les sous-tableaux vides lorsque k vaut 0. Pour [1, -1, 0], le résultat est 6 au lieu de 3.
Utiliser un ensemble de sommes préfixes à la place d’une map de comptage sous-estime les répétitions. Pour [0, 0, 0] et k = 0, la réponse est 6, car chaque occurrence antérieure de la même somme préfixe commence un sous-tableau différent.
Dans la méthode par force brute, sortir de la boucle interne lorsque le total dépasse k est incorrect pour la même raison que pour la fenêtre glissante.

Questions fréquentes4

Quelle est la complexité temporelle de « Subarray Sum Equals K » ?

La solution utilisant les sommes préfixes et une table de hachage s’exécute en O(n) temps et utilise O(n) d’espace supplémentaire : un seul parcours, avec une recherche et une mise à jour par élément. Vérifier chaque sous-tableau à l’aide d’un total courant prend O(n²) en temps, et recalculer la somme de chaque sous-tableau depuis zéro prend O(n³).

Pourquoi une fenêtre glissante ne fonctionne-t-elle pas pour « Somme d’un sous-tableau égale à K » ?

Une fenêtre glissante repose sur le fait que la somme augmente quand la fenêtre s’agrandit et diminue quand elle rétrécit, ce qui n’est vrai que si toutes les valeurs sont positives. Avec des valeurs négatives, une fenêtre dont la somme est déjà trop élevée peut tout de même devenir une correspondance si elle s’agrandit davantage ; aucune règle ne vous indique donc quand déplacer le bord gauche. Si toutes les valeurs étaient positives, une fenêtre glissante résoudrait le problème en O(n) temps et en O(1) espace.

Pourquoi la table de hachage commence-t-elle par associer 0 à 1 ?

Cette entrée représente le préfixe vide avant le premier élément, dont la somme est 0. La somme d’un sous-tableau qui commence à l’indice 0 est égale à la somme du préfixe actuel moins ce préfixe vide ; sans cette entrée, ces sous-tableaux ne sont jamais comptabilisés. Pour nums = [5] et k = 5, la recherche de 5 - 5 = 0 trouve cette entrée et renvoie 1.

Peut-on résoudre le problème de la somme d’un sous-tableau égale à K avec un espace supplémentaire en O(1) ?

Pas avec la méthode en un seul passage. Pour compter les correspondances qui se terminent à un élément, tu dois savoir quelles sommes préfixes l’ont précédé, et il peut y en avoir jusqu’à n+1 différentes. Sans la map, tu retombes sur le total cumulatif en O(n²). Lorsque toutes les valeurs sont positives, une fenêtre glissante compte les sous-tableaux en O(n) temps et O(1) espace.

Python

def subarraySum(nums, k):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

nums = [3, 4, -7, 1, 3, 3, 1, -4]
k = 7

Attendu