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).
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.