Overview
La technique deux-pointeurs utilise deux index se déplaçant vers l'intérieur ou vers l'avant pour résoudre des problèmes sur des tableaux/chaînes en O(n).
Analogy
Comme deux personnes marchant l'une vers l'autre sur une route — elles se rencontrent au milieu.
Step-by-step
- Place gauche=0 et droite=len-1
- En boucle tant que gauche < droite
- Vérifie la condition et déplace le pointeur approprié
- Stop quand ils se rencontrent
Visual
tableau=[1,2,3,4,5,6], cible=7
g=0(1), d=5(6) → 7 ✓
g=1(2), d=4(5) → 7 ✓
g=2(3), d=3(4) → 7 ✗
Common mistakes
- Ne pas trier d'abord si l'ordre est requis
- Conditions de déplacement de pointeur incorrectes
Practice questions
- Trouve toutes les paires avec une somme cible dans un tableau trié
- Supprime les doublons dans un tableau trié en place