Formations — 1 037 leçons en français

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 : g ne 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 le for i in range(len(t)) suivi de t[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.

Lire l'explication détaillée et faire le quiz →

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.