- Le rituel TAP. Invariant, variant, conclusion, complexité — c00, pas 1. Cette sheet ne redémontre pas le rituel, elle l'instancie une fois.
- Invariant = conteneur + tranche + « exactement ». c00, pas 2. Ici le conteneur est l'accumulateur et la tranche est la fenêtre.
- Variant = entier ≥ 0 strictement décroissant. c00, pas 3. La ligne « fenêtre glissante » de son tableau est exactement ce pas-ci.
- Tranche demi-ouverte.
nums[a:b]= indices a … b−1, borne droite exclue, notée [a:b). La fenêtre de bords l et r estnums[l:r+1], jamaisnums[l:r]. - Amortissement. Un coût O(1) amorti se justifie par un argument de comptage global (« chaque élément entre une fois, sort au plus une fois »), il ne se décrète pas — c00, pas 5.
nums[l] fait baisser la somme. Cette hypothèse est ce qui tombe au pas 7.
H4On énonce le squelette — les deux lignes de contrôle — et les quatre phrases. Le corps se remplit devant l'interlocuteur : une sheet de coding ne contient jamais la solution complète.
La chaîne
Le signal, et le contre-signal tronc
Trois marques dans l'énoncé déclenchent la fenêtre : le mot contigu (sous-tableau, sous-chaîne), un extremum de longueur (« le plus long », « le plus court »), et une condition monotone en la taille.
Monotone se lit sur l'accumulateur : avec des valeurs positives la somme ne fait que monter quand la fenêtre grandit ; avec un compte (fréquences, distincts) le compte ne fait que monter aussi. Le contre-signal est net : des négatifs avec une somme cible — agrandir peut faire baisser la somme, la monotonie tombe.
« L'énoncé dit contigu et la condition est monotone en la taille, donc agrandir puis rétrécir suffit à explorer toutes les fenêtres utiles, donc deux indices qui n'avancent que vers la droite. »
Énoncé. « Plus petite longueur d'un sous-tableau contigu dont la somme est ≥ target ; 0 s'il n'y en a pas », avec nums à valeurs > 0.
Les trois marques. « sous-tableau contigu » → segment ; « plus petite longueur » → extremum de longueur ; « somme ≥ target » + valeurs > 0 → monotone croissante en la taille.
Fil rouge. nums = [2, 3, 1, 2, 4, 3], target = 7. Réponse : 2, réalisée par [4, 3] aux indices 4 et 5 — vérifiée contre une force brute sur les 21 sous-tableaux.
Ce qui n'est pas le signal. « sous-séquence » (non contiguë) : ni fenêtre ni deux pointeurs. « k-ième plus grand » : un tas. « somme exactement égale à target » avec des négatifs : préfixes + dictionnaire (LC 560, c10), pas une fenêtre.
Le pattern : deux lignes de contrôle, rien d'autre tronc
Deux indices l ≤ r. r avance à chaque tour, sans condition. l avance seulement pour rétablir la condition, dans un while. Un accumulateur décrit exactement la tranche [l:r+1).
while · acc = f(nums[l:r+1)) exactementDeux lignes seulement changent d'un problème à l'autre : ce qu'on ajoute quand nums[r] entre, ce qu'on retire quand nums[l] sort. La condition du while est le troisième et dernier point de variation.
« r avance à chaque tour et l ne bouge que pour rétablir la condition, donc chaque élément entre une fois et sort au plus une fois, donc deux lignes de contrôle suffisent à décrire tout le pattern. »
s est le conteneur de l'invariant, (n−r) + (n−l) est le variant, et le couple s += v / s −= nums[l] est ce qui préserve l'invariant.
L'ordre à l'intérieur du while n'est pas libre. On enregistre puis on rétrécit : la fenêtre est valide à l'entrée du corps, elle ne l'est plus forcément après. Inverser les deux lignes, c'est enregistrer une fenêtre dont on ne sait rien.
L'invariant : exact, puis ancré à droite tronc
L'invariant se dit à la sortie du while, pour chaque r, et il a trois morceaux : l'accumulateur est exact sur la tranche, la fenêtre est dans l'état que le while garantit, et l'optimum partiel est ancré à droite.
« Ancré à droite » est le morceau qu'on oublie, et c'est lui qui porte toute la preuve : on ne raisonne jamais sur toutes les fenêtres à la fois, seulement sur celles qui finissent au bord droit courant. La réunion sur tous les r vient à la conclusion, pas avant.
« L'accumulateur est exact sur la tranche et le while a rétabli la condition, donc pour ce bord droit je connais déjà la meilleure fenêtre qui y finit, donc l'optimalité est ancrée à droite, tour par tour. »
À la sortie du while, pour chaque r :
I1. s = Σ nums[l:r+1] exactement.
I2. s < target — la fenêtre courante n'est plus valide, c'est ce que le while vient d'obtenir.
I3. best = longueur de la plus courte fenêtre de somme ≥ target finissant en un r′ ≤ r (+∞ s'il n'y en a pas).
Initialisation : avant le premier tour, l = 0, r = −1, la tranche [0:0) est vide, s = 0 et best = +∞ — I1, I2, I3 tiennent.
Préservation : s += v étend la tranche à [l:r+1) et garde I1 ; le while enregistre toutes les fenêtres valides finissant en r par longueur décroissante, donc la plus courte, puis sort quand s < target, ce qui rétablit I2.
I1, I2, I3 vérifiés à l'exécution à la sortie de chaque while sur 20 000 entrées aléatoires (longueurs 0 à 7, valeurs 1 à 9, cibles 1 à 30) : le résultat coïncide avec la force brute sur les 20 000, sans exception.
nums = [2, 3, 1, 2, 4, 3], target = 7. Le cadre vert est la fenêtre courante [l:r+1) ; le fond ambré est la meilleure fenêtre enregistrée jusqu'ici. Fais « pas › » et regarde l : il ne recule jamais. Six avancées de r, cinq de l — chaque élément entre une fois et sort au plus une fois. La ligne du bas est l'invariant, réécrit à chaque image ; dis-le avant de le lire.
Le variant, et l'amortissement qui donne le O(n)
Le variant est (n − r) + (n − l) : entier, ≥ 0, et strictement décroissant dès qu'un des deux pointeurs avance — donc à chaque tour de la boucle et à chaque tour du while.
Le while imbriqué ne coûte pas O(n) par tour : on ne compte pas les avancées de l par tour, on les compte globalement. C'est l'amortissement, et il se justifie en une phrase — chaque élément entre une fois, sort au plus une fois.
« Le variant décroît strictement dès qu'un pointeur avance, donc la boucle termine ; et l ne recule jamais, donc ses avancées sont au plus n au total, donc le coût est linéaire malgré le while imbriqué. »
Compté sur le code instrumenté, nums = [2, 3, 1, 2, 4, 3] (n = 6) : r avance 6 fois, l avance 5 fois — 11 mouvements de pointeur au total, contre 21 sous-tableaux à sommer pour la force brute.
| n | fenêtre — ≤ 2n mouvements | force brute — n(n+1)/2 sous-tableaux |
|---|---|---|
| 6 | 12 | 21 |
| 10 | 20 | 55 |
| 100 | 200 | 5 050 |
| 1 000 | 2 000 | 500 500 |
Temps. ≤ 2n avancées × O(1) par avancée (une addition, une soustraction, une comparaison) donc O(n). Espace. Trois entiers, O(1) — pour l'habit « budget » ce sera O(|Σ|), la taille de l'alphabet, jamais le nombre de caractères vus à l'exécution.
Le piège du variant. Si une branche du corps n'avance ni l ni r, le variant ne décroît pas : c'est là, et nulle part ailleurs, que la boucle infinie attend.
La conclusion : la réunion sur les bords droits
À la sortie de la boucle, r vaut n − 1. On instancie I3 à cette valeur : best est optimal parmi les fenêtres finissant en un r′ ≤ n − 1.
C'est le seul endroit où l'on parle de toutes les fenêtres : les n familles « fenêtres finissant en r′ » recouvrent l'ensemble des fenêtres, et un minimum de minima est le minimum.
« I3 instancié en r = n − 1 donne l'optimum sur chaque bord droit, donc, comme toute fenêtre a un bord droit, l'optimum sur la réunion, donc best est la plus courte fenêtre valide tout court. »
Sortie avec best fini. I3 en r = n − 1 : best est la plus courte fenêtre de somme ≥ target finissant en un r′ quelconque. Donc c'est la plus courte, tous bords droits confondus. Sur le fil rouge : best = 2, réalisée par [4, 3].
Sortie avec best = +∞. Aucune fenêtre valide ne finit en aucun r′, donc il n'en existe aucune, donc on renvoie 0. La ligne retour best si fini, sinon 0 n'est pas une précaution : c'est la deuxième conclusion.
À ne pas dire. « Donc on a balayé tout le tableau » : vrai, et sans rapport avec la justesse du résultat. La conclusion porte sur best, pas sur le parcours.
Là où l'ancrage à droite se voit. À l'image 10 de la figure 1, best passe à 3 sur [1, 2, 4] ; à l'image 15 il passe à 2 sur [4, 3]. À aucun moment on n'a comparé ces deux fenêtres entre elles — chacune a été la meilleure de son propre bord droit.
Trois habits sur un seul squelette
Ce qui change entre les trois habits est la condition du while et l'accumulateur. Les deux lignes de contrôle — r avance toujours, l avance pour rétablir — ne changent jamais.
Fixe et variable cherchent des choses opposées et se trahissent par le sens du while. L'habit « budget » rétrécit d'un seul cran, jamais dans une boucle : la fenêtre ne peut plus grandir, elle n'a pas besoin de raccourcir.
« Le squelette est le même dans les trois habits, donc seule la condition du while et l'accumulateur distinguent fixe, variable et budget, donc reconnaître l'habit suffit à écrire le corps. »
Fixe — LC 643, moyenne maximale sur k éléments. On maintient r − l + 1 = k : nums[r] entre, nums[r−k] sort. Invariant : « s = somme des k derniers, exactement ». Sur le fil rouge avec k = 3, les sommes glissantes sont 6, 6, 7, 9 ; maximum 9, donc moyenne maximale 3. O(n) temps, O(1) espace.
Variable — LC 209, le fil rouge. On rétrécit tant que la fenêtre est valide, pour attraper la plus courte.
Budget — LC 424, plus longue sous-chaîne à ≤ k remplacements. Fenêtre valide ⇔ (r − l + 1) − maxfreq ≤ k. On rétrécit d'un cran quand elle est invalide, pour attraper la plus longue.
L'astuce à savoir dire. maxfreq n'est jamais décrémenté quand un caractère sort. Elle peut donc être surestimée — mais une fenêtre ne s'allonge que si elle bat le record, et au moment où elle le bat maxfreq est juste. Vérifié à l'exécution : 0 désaccord sur 20 000 chaînes aléatoires face à la version qui recalcule le maximum à chaque tour.
| habit | accumulateur | le while | temps · espace |
|---|---|---|---|
| fixe (LC 643) | s, somme des k derniers | pas de while : l = r − k + 1 | O(n) · O(1) |
| variable (LC 209) | s, somme de [l:r+1) | tant que valide : enregistrer, rétrécir | O(n) · O(1) |
| budget (LC 424) | cnt + maxfreq | si invalide : rétrécir d'un cran | O(n) · O(|Σ|) |
Huit images : les sept tours, puis la conclusion. Le budget se lit dans l'invariant : la ligne du bas est (r − l + 1) − maxfreq ≤ 1, le nombre de caractères à remplacer. Le fond ambré est la fenêtre témoin du record ; réponse 4, atteinte au tour r = 3 sur AABA. À la dernière image, maxfreq vaut encore 3 alors que la fenêtre n'a plus que 2 A — c'est le non-décrément, et il est sans effet puisque best est déjà acquis.
Où ça casse casse
Le pattern casse par le haut — H2 tombe, la monotonie est fausse et le résultat est faux sans que rien ne plante — ou par le bas, sur quatre lignes de code qui ont toutes l'air justes.
Le cas fatal est le seul à ne pas lever d'exception : des négatifs avec une somme cible. La fenêtre rend une réponse, et elle est fausse.
« Avec un négatif, retirer un élément peut faire monter la somme, donc rétrécir n'est plus une réparation, donc l devrait pouvoir reculer, donc le pattern ne s'applique pas — il faut des préfixes et un dictionnaire, ou une deque monotone. »
nums = [2, −3, 4], target = 4. La bonne réponse est 1 : le sous-tableau [4]. Le squelette du pas 2 renvoie 0 — « aucune fenêtre ».
Pourquoi. Les sommes préfixes valent 2, puis −1, puis 3 : s ne dépasse jamais 4, le while ne s'ouvre jamais, l reste à 0. Le −3 empoisonne toutes les fenêtres qui commencent en 0, et seul un recul de l — interdit — les en sortirait.
Le remède n'est pas une rustine. Somme exactement égale : sommes préfixes + dictionnaire (LC 560), O(n). Somme ≥ cible avec des négatifs : préfixes + deque monotone, O(n). Ce sont d'autres invariants, donc une autre sheet : c10 · Préfixes et deque monotone.
Le test de trente secondes. Avant d'écrire la première ligne : « si j'agrandis la fenêtre, est-ce que mon accumulateur ne peut aller que dans un sens ? » Non ⇒ pas de fenêtre glissante.
ifau lieu dewhilepour rétrécir. Un seul cran retiré par tour : la fenêtre reste trop longue etbestest surestimé. L'habit budget veut bien unif, l'habit variable veut unwhile— le sens de la recherche décide, jamais l'habitude.- Enregistrer
bestaprès avoir rétréci. La fenêtre est valide à l'entrée du corps duwhile, plus après. Inverser les deux lignes, c'est mesurer une fenêtre dont l'invariant ne dit plus rien. - Tranche décalée d'un. La fenêtre est
nums[l:r+1], pasnums[l:r]: la borne droite est exclue. Écrire l'invariant avec la tranche, en demi-ouvert, est le seul moyen fiable de ne pas se tromper de 1. best = 0pour un minimum. Unmins'initialise à+inf(math.inf), unmaxà 0 ou−inf. Avecbest = 0,min(0, …)vaut 0 pour toujours et le cas « aucune fenêtre » disparaît au lieu d'être traité.maxfreqrecalculé à chaque tour.max(cnt.values())dans la boucle coûte O(|Σ|) par tour : le pattern reste juste mais la complexité annoncée devient fausse. Le non-décrément n'est pas une optimisation cosmétique, c'est ce qui tient le O(n).
Résumé
- Signal : contigu + extremum de longueur + condition monotone en la taille — avec des positifs ou des comptes.
- Pattern : r avance toujours ; l avance dans un
whilepour rétablir la condition ; l'accumulateur décrit exactement [l:r+1). - Invariant ancré à droite : à chaque r, on a l'optimum parmi les fenêtres qui finissent en r. Jamais l'optimum global avant la fin.
- Variant (n−r) + (n−l) ; amortissement : chaque élément entre une fois, sort au plus une fois ⇒ O(n).
- Trois habits : fixe (taille imposée), variable (rétrécir tant que valide), budget (rétrécir d'un cran quand invalide,
maxfreqnon décrémenté). - Négatifs + somme cible ⇒ pas de fenêtre glissante :
[2, −3, 4],target = 4renvoie 0 au lieu de 1.
Chaîne verbalisée — une prise, à voix haute
- Quel signal déclenche la fenêtre glissante, et lequel l'interdit ?Contigu, extremum de longueur, condition monotone en la taille — avec des positifs ou des comptes. L'interdit : des négatifs avec une somme cible, la monotonie tombe.
- Énonce l'invariant de LC 209, avec sa tranche.À la sortie du while, pour chaque r : s = Σ nums[l:r+1] exactement ; s < target ; et best est la plus courte fenêtre de somme ≥ target finissant en un r′ ≤ r.
- Le variant, et pourquoi O(n) malgré le while imbriqué ?(n − r) + (n − l) : entier, ≥ 0, décroît dès qu'un pointeur avance. r avance n fois, l au plus n fois au total — chaque élément entre une fois et sort au plus une fois. Donc ≤ 2n opérations O(1).
- La conclusion, en commençant par donc.Donc en r = n − 1, best est optimal sur chaque bord droit ; toute fenêtre a un bord droit, donc best est la plus courte fenêtre valide tout court ; et +inf veut dire qu'il n'en existe aucune, donc 0.
- L'astuce de LC 424 ?maxfreq n'est jamais décrémenté quand un caractère sort, et la fenêtre ne rétrécit que d'un cran. maxfreq peut être surestimée, mais elle est juste au moment où la fenêtre bat le record — le seul moment qui compte.
Ponts et cartes
coding::fenetre-glissante (le signal, les trois habits, la condition du while) · coding::deux-pointeurs (l ne recule jamais, le variant à deux termes) · coding::amortissement (chaque élément entre une fois et sort au plus une fois ⇒ O(n) malgré la boucle imbriquée).
Une carte qui résiste après cette chaîne est une carte à refondre, pas une section à relire.