Accueil › Python › Deux pointeurs et fenêtre glissante
Deux pointeurs et fenêtre glissante
Algorithmique d'entretienavance
Deux index bien placés remplacent une double boucle : O(n²) devient O(n). Trois variantes couvrent presque tout.
Convergents, sur une liste triée :
def deux_montants(tries: list[int], cible: int) -> tuple[int, int] | None:
g, d = 0, len(tries) - 1
while g < d:
s = tries[g] + tries[d]
if s == cible:
return g, d
if s < cible:
g += 1 # trop petit → augmenter
else:
d -= 1 # trop grand → diminuer
return None
Lecture / écriture, pour filtrer en place en O(1) d'espace :
def sans_doublons(tries: list[int]) -> int:
"""Déduplique une liste triée sur place ; renvoie la longueur utile."""
if not tries:
return 0
ecriture = 1
for lecture in range(1, len(tries)):
if tries[lecture] != tries[ecriture - 1]:
tries[ecriture] = tries[lecture]
ecriture += 1
return ecriture
Fenêtre glissante, pour les énoncés « la plus longue suite contiguë qui… » :
def plus_longue_sans_repetition(paniers: list[str]) -> int:
vus: dict[str, int] = {}
g = meilleur = 0
for d, p in enumerate(paniers):
if p in vus and vus[p] >= g:
g = vus[p] + 1 # on saute juste après la précédente occurrence
vus[p] = d
meilleur = max(meilleur, d - g + 1)
return meilleur
Le réflexe Python par-dessus tout cela : on se déplace par index, jamais par tranches. t = t[1:] dans une boucle recopie le reste de la liste à chaque tour et ruine le O(n).
Les termes à connaître
- Deux pointeurs convergents
Deux index partant des extrémités (
g = 0,d = len(t) - 1) et se rapprochant. Suppose presque toujours une liste triée : c'est le tri qui rend le déplacement décidable. Coût O(n) après tri.- Pointeur de lecture et pointeur d'écriture
Deux index qui avancent dans le même sens : l'un lit, l'autre note où écrire le prochain élément conservé. C'est le schéma des filtrages en place, en O(n) temps et O(1) espace.
- Lièvre et tortue
Deux pointeurs de vitesses différentes (un pas contre deux). Sert à détecter un cycle, ou à trouver le milieu d'une séquence en un seul passage.
- Fenêtre glissante
Un intervalle contigu
[g, d]qu'on étend par la droite et qu'on rétrécit par la gauche. Résout les énoncés « la plus longue / la plus courte suite contiguë qui… » en O(n).- Analyse amortie
Le raisonnement qui prouve qu'une fenêtre glissante est O(n) malgré sa boucle imbriquée :
gne recule jamais, donc sur toute l'exécution il avance au plus n fois. Chaque élément entre une fois et sort au plus une fois.- enumerate
for i, x in enumerate(t)donne l'index et la valeur. Évite lefor i in range(len(t))suivi det[i], plus long à écrire et plus facile à décaler d'un cran.- Échange simultané
t[g], t[d] = t[d], t[g]échange deux éléments sans variable temporaire. Le côté droit est évalué entièrement avant toute affectation, ce qui rend l'opération sûre.
Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.