Formations — 1 037 leçons en français

Accueil › Coding & algorithmique › La technique des deux pointeurs

La technique des deux pointeurs

Tableaux et parcoursdebutant

Deux indices bien placés transforment un O(n²) en O(n). Trois variantes couvrent presque tous les cas.

Convergents — sur un tableau trié :

// Deux éléments de somme cible
static int[] sommeDeux(int[] trie, int cible) {
    int g = 0, d = trie.length - 1;
    while (g < d) {
        int s = trie[g] + trie[d];
        if (s == cible) return new int[]{g, d};
        if (s < cible) g++;          // trop petit : augmenter
        else d--;                     // trop grand : diminuer
    }
    return new int[]{-1, -1};
}

Parallèles — lecture et écriture, pour modifier en place :

// Supprimer les doublons d'un tableau trié, en place ; renvoie la nouvelle longueur
static int dedoublonner(int[] t) {
    if (t.length == 0) return 0;
    int ecriture = 1;
    for (int lecture = 1; lecture < t.length; lecture++)
        if (t[lecture] != t[ecriture - 1]) t[ecriture++] = t[lecture];
    return ecriture;
}

Lièvre et tortue — vitesses différentes :

// Cycle dans une liste chaînée, en O(1) espace
static boolean aUnCycle(Noeud tete) {
    Noeud lent = tete, rapide = tete;
    while (rapide != null && rapide.suivant != null) {
        lent = lent.suivant;
        rapide = rapide.suivant.suivant;
        if (lent == rapide) return true;
    }
    return false;
}

Le prérequis à vérifier : les pointeurs convergents supposent un tableau trié. Si l'entrée ne l'est pas, une HashMap en O(n) bat souvent le tri en O(n log n) — et conserve les index d'origine.

Les termes à connaître

Deux pointeurs convergents

Un indice part du début, l'autre de la fin, et ils se rapprochent. Sur un tableau trié, chaque comparaison élimine définitivement une possibilité : O(n) au lieu de O(n²).

Deux pointeurs parallèles

Deux indices qui avancent dans le même sens, à des rythmes différents — souvent un en lecture et un en écriture, ou un rapide et un lent.

Lièvre et tortue

Deux pointeurs à vitesses différentes (un pas / deux pas). Détecte un cycle dans une liste chaînée et trouve l'élément du milieu en un seul parcours.

Condition d'avancement

La règle qui décide quel pointeur bouge. C'est là qu'est toute la justesse de l'algorithme — et l'erreur quand il boucle sans fin.

Prérequis de tri

Les pointeurs convergents supposent presque toujours un tableau trié. Si l'entrée ne l'est pas, trier coûte O(n log n) — parfois moins bon qu'une HashMap en O(n).

Partition

Réorganiser un tableau selon un critère (pairs avant impairs, plus petits avant plus grands) avec deux pointeurs, en place et en O(n).

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.