Minimum Size Subarray Sum

Q: Quelle est la complexité temporelle de la somme d’un sous-tableau de taille minimale ?

La solution par fenêtre glissante s’exécute en temps O(n) et utilise un espace O(1) . La boucle interne pourrait laisser penser que sa complexité est quadratique, mais left avance uniquement, donc, sur l’ensemble de l’exécution, il se déplace au plus n fois. La version avec somme préfixe est en O(n log n) , et vérifier chaque point de départ est en O(n²) .

Q: Pourquoi apprendre la solution par somme préfixe en O(n log n) s’il en existe une en O(n) ?

Les intervieweurs le demandent souvent après la réponse en O(n) . Cela montre une deuxième utilisation des valeurs positives : les sommes préfixes sont triées, donc une recherche binaire trouve où un total courant dépasse un seuil pour la première fois. Cet outil revient dans d’autres problèmes, par exemple pour choisir un indice au hasard proportionnellement à son poids.

Q: La somme du sous-tableau doit-elle être exactement égale à la cible ?

Non. Toute somme supérieure ou égale à target compte. Avec target = 15 , la fenêtre 9, 3, 7 totalise 19 et a toujours une longueur de 3. Si tu as plutôt besoin d’une somme exacte, la fenêtre fonctionne toujours pour les valeurs positives : réduis-la tant que la somme est supérieure à la cible, et note une longueur uniquement lorsqu’elle est égale à celle-ci.

MoyenFenêtre glissante Sommes préfixes

+10

Vous recevez un entier positif target et un tableau nums d’entiers positifs. Trouvez le sous-tableau le plus court (une suite d’éléments voisins) dont la somme est supérieure ou égale à target, et renvoyez sa longueur. Si aucun sous-tableau n’atteint target, renvoyez 0.

Fonction

minSubArrayLen(target: integer, nums: integer-array) → integer

targetinteger: la somme qu'un sous-tableau doit atteindre ou dépasser
numsinteger-array: le tableau d’entiers positifs
Renvoieinteger: la longueur du plus court sous-tableau dont la somme est supérieure ou égale à target, ou 0 si aucun n’existe

Contraintes

1 ≤ target ≤ 10⁹
1 ≤ nums.length ≤ 2 × 10⁴
1 ≤ nums[i] ≤ 10⁴

Exemples

Entrée: target = 15nums = [4, 2, 9, 3, 7, 1, 5]
Sortie: 3
Explication: Aucun couple de voisins n’atteint 15 : la plus grande somme de deux nombres voisins est 9 + 3 = 12. Trois nombres voisins y parviennent : 4 + 2 + 9 = 15 et 9 + 3 + 7 = 19, donc la réponse est 3.

+16 tests cachés à la soumission

Pour aller plus loin

Comment résoudrais-tu le problème si nums pouvait aussi contenir des zéros et des nombres négatifs, ce qui rendrait la fenêtre glissante inopérante ?

Indices

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

0 sur 3 ouverts

Solution

Les valeurs sont toutes positives ; étendre un sous-tableau augmente donc toujours sa somme, tandis que le réduire la diminue toujours. Ce simple fait est à la base des deux solutions rapides. Les sommes préfixes forment une liste triée ; une recherche binaire permet donc de trouver où une somme atteint target pour la première fois. Mieux encore, la meilleure fin ne se déplace jamais vers la gauche quand le début se déplace vers la droite ; une seule fenêtre, qui s'agrandit à droite et se réduit à gauche, trouve donc la réponse en un seul passage.

Étends-toi à partir de chaque début

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Fixez un indice de départ et ajoutez les valeurs une par une vers la droite. La première fois que la somme cumulée atteint target, vous avez le sous-tableau le plus court qui commence à cet indice : tous les sous-tableaux plus courts s’arrêtaient plus tôt et leur somme était encore trop faible. Enregistrez donc sa longueur, arrêtez de l’étendre et passez au départ suivant. La réponse est la longueur minimale parmi tous les départs.

Avec target = 15 et [4, 2, 9, 3, 7, 1, 5], au départ 0, les sommes sont 4, 6, 15 et on s’arrête à la longueur 3. Au départ 1, les sommes sont 2, 11, 14, 21 et on s’arrête à la longueur 4. Au départ 2, les sommes sont 9, 12, 19, soit à nouveau une longueur de 3. Aucun départ ne fait mieux que 3.

Le problème survient lorsque la cible est difficile à atteindre. Si aucun sous-tableau ne l’atteint, chaque départ parcourt tout le reste du tableau : n(n+1)/2 additions, soit 2 × 10^8 pour n = 2 × 10^4. Chaque départ recalcule également des sommes déjà obtenues au départ précédent.

Algorithme

Définis best à 0, ce qui signifie que rien n’a encore été trouvé.
Pour chaque indice de départ, définis une somme cumulée à 0.
Déplace un indice de fin vers la droite à partir du début, en ajoutant nums[end] à la somme.
Lorsque la somme atteint target, conserve end-start+1 si cette valeur dépasse best, puis arrête d’étendre ce départ.
Retourne best.

def minSubArrayLen(target, nums):
    n = len(nums)
    best = 0  # 0 means no subarray found yet
    for start in range(n):
        total = 0
        for end in range(start, n):
            total += nums[end]
            if total >= target:
                # The shortest subarray from this start ends here
                if best == 0 or end - start + 1 < best:
                    best = end - start + 1
                break
    return best

Sommes préfixes et recherche binaire

Intuition

Soit prefix[k] la somme des k premières valeurs, avec prefix[0] = 0. La somme de nums[start..end-1] est alors prefix[end] - prefix[start]. Pour un début fixé, on cherche le plus petit end tel que prefix[end] ≥ prefix[start] + target.

Toutes les valeurs sont positives, donc prefix est strictement croissant, et on peut trouver par recherche binaire la première position où il atteint une valeur. Pour [4, 2, 9, 3, 7, 1, 5], prefix vaut [0, 4, 6, 15, 18, 25, 26, 31]. À partir du début 2, il faut 6 + 15 = 21 ; la première valeur de prefix supérieure ou égale à 21 est 25 à l’indice 5, donc la fenêtre est nums[2..4] = 9, 3, 7, de longueur 3.

Si même prefix[n] est inférieur à ce dont un début a besoin, aucun end ne convient, et aucun ne conviendra non plus pour un début ultérieur, puisque prefix[start] ne fait qu’augmenter. Arrêtez-vous là. Cela représente n recherches binaires, un temps de O(n log n), plus O(n) pour le tableau des sommes préfixes. La plus grande valeur comparée est 2 × 10^8 + 10^9, ce qui tient dans un entier de 32 bits.

Algorithme

Construis prefix de longueur n+1, avec prefix[k+1] = prefix[k] + nums[k].
Pour chaque début, calcule need = prefix[start] + target.
Si prefix[n] < need, arrête-toi : aucun début ultérieur ne peut réussir.
Effectue une recherche dichotomique entre les positions start+1 et n pour trouver le premier end tel que prefix[end] ≥ need, et conserve end-start si c’est la longueur la plus courte jusqu’à présent.
Renvoie la longueur la plus courte, ou 0 si aucun début n’a réussi.

from bisect import bisect_left


def minSubArrayLen(target, nums):
    n = len(nums)
    # prefix[k] is the sum of the first k values; it only grows
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    best = 0
    for start in range(n):
        need = prefix[start] + target
        if prefix[n] < need:
            break  # no window from here on can reach target
        # The first end with prefix[end] >= need closes the shortest window
        end = bisect_left(prefix, need, start + 1)
        if best == 0 or end - start < best:
            best = end - start
    return best

Fenêtre glissante

Intuition

Conservez une fenêtre nums[left..right] et sa somme. Avancez right d’un pas à la fois et ajoutez la nouvelle valeur. Tant que la somme est supérieure ou égale à target, la fenêtre est candidate : notez sa longueur, puis retirez nums[left] et avancez left pour voir si une fenêtre plus courte fonctionne encore.

Pourquoi left peut-il sortir définitivement ? Lorsque la fenêtre nums[left..right] atteint target pour la première fois, la fenêtre plus petite nums[left..right-1] ne l’atteignait pas, car la boucle l’aurait réduite à l’étape précédente. Ainsi, right est la fin la plus précoce pour ce début, et toute fin ultérieure ne donne qu’un sous-tableau plus long. Ce début a fourni sa meilleure réponse. Ce raisonnement nécessite des valeurs positives : avec un nombre négatif, une fenêtre plus longue pourrait avoir une somme plus grande par la suite.

Avec target = 15 et [4, 2, 9, 3, 7, 1, 5] : la somme augmente de 4 à 6, puis à 15 ; on note donc une longueur de 3 et 4 sort (11). L’ajout de 3 donne 14, l’ajout de 7 donne 21 : on note une longueur de 4, on retire 2 (19), on note une longueur de 3, puis on retire 9 (10). L’ajout de 1 et de 5 donne 16 : on note une longueur de 4, puis on retire 3 (13). La réponse est 3.

La boucle while se trouve à l’intérieur de la boucle for, mais chaque indice entre dans la fenêtre une fois et en sort une fois ; le travail total est donc de O(n). Seuls trois nombres sont stockés, ce qui représente un espace de O(1).

Algorithme

Définis left = 0, total = 0 et best = 0.
Pour chaque right, ajoute nums[right] à total.
Tant que total ≥ target, conserve right-left+1 si cette valeur est supérieure à best, soustrais nums[left] et déplace left d’un cran vers la droite.
Retourne best, qui vaut toujours 0 si la somme n’a jamais atteint target.

def minSubArrayLen(target, nums):
    best = 0  # 0 means no window found yet
    total = 0  # sum of nums[left .. right]
    left = 0
    for right in range(len(nums)):
        total += nums[right]
        # Shrink while the window still reaches target
        while total >= target:
            if best == 0 or right - left + 1 < best:
                best = right - left + 1
            total -= nums[left]
            left += 1
    return best

Pièges et cas limites

La plupart des bugs se trouvent dans l’étape de réduction de la fenêtre et dans la valeur renvoyée quand aucune fenêtre n’atteint target.

Réduire la fenêtre avec if au lieu de while. Pour target = 12 et [1, 1, 2, 3, 12], l’ajout de 12 porte la somme à 19. Un if enregistre une longueur de 5, retire une valeur et passe à la suite, de sorte que la fenêtre [12] de longueur 1 n’est jamais mesurée. Une boucle continue à retirer des valeurs tant que la somme est suffisante.
Enregistrer la longueur après avoir retiré nums[left] au lieu de le faire avant. La fenêtre mesurée doit être celle dont la somme a atteint target.
Comparer avec > au lieu de ≥. Un sous-tableau dont la somme est égale à target compte : [3, 3, 3] avec target = 9 a pour réponse 3, et non 0.
Renvoyer la valeur sentinelle. Si tu initialises best à n+1 ou à l’infini, remplace cette valeur par 0 si aucune fenêtre n’a atteint target.
Réutiliser la fenêtre avec des tableaux contenant des zéros ou des nombres négatifs. Cette approche suppose que chaque valeur est positive ; ce problème le garantit, mais pas ses variantes.

Questions fréquentes4

Quelle est la complexité temporelle de la somme d’un sous-tableau de taille minimale ?

La solution par fenêtre glissante s’exécute en temps O(n) et utilise un espace O(1). La boucle interne pourrait laisser penser que sa complexité est quadratique, mais left avance uniquement, donc, sur l’ensemble de l’exécution, il se déplace au plus n fois. La version avec somme préfixe est en O(n log n), et vérifier chaque point de départ est en O(n²).

Pourquoi la fenêtre glissante a-t-elle besoin de nombres positifs ?

Réduire la fenêtre doit diminuer sa somme et l’agrandir doit l’augmenter, sinon retirer l’élément de gauche pourrait éliminer le début de la réponse. Avec des nombres négatifs, cet ordre ne tient plus. La solution habituelle consiste à utiliser des sommes préfixes avec une deque monotone de débuts candidats, ce qui s’exécute toujours en O(n).

Pourquoi apprendre la solution par somme préfixe en O(n log n) s’il en existe une en O(n) ?

Les intervieweurs le demandent souvent après la réponse en O(n). Cela montre une deuxième utilisation des valeurs positives : les sommes préfixes sont triées, donc une recherche binaire trouve où un total courant dépasse un seuil pour la première fois. Cet outil revient dans d’autres problèmes, par exemple pour choisir un indice au hasard proportionnellement à son poids.

La somme du sous-tableau doit-elle être exactement égale à la cible ?

Non. Toute somme supérieure ou égale à target compte. Avec target = 15, la fenêtre 9, 3, 7 totalise 19 et a toujours une longueur de 3. Si tu as plutôt besoin d’une somme exacte, la fenêtre fonctionne toujours pour les valeurs positives : réduis-la tant que la somme est supérieure à la cible, et note une longueur uniquement lorsqu’elle est égale à celle-ci.

Python

def minSubArrayLen(target, nums):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

target = 15
nums = [4, 2, 9, 3, 7, 1, 5]

Attendu

Minimum Size Subarray Sum

Fonction

Contraintes

Exemples

Indices

Solution

Étends-toi à partir de chaque début

Sommes préfixes et recherche binaire

Fenêtre glissante

Pièges et cas limites

Questions fréquentes4

Problèmes similaires