Qu'est-ce que la technique des deux pointeurs ?

Question

Accepted Answer

La technique des **deux pointeurs** utilise deux indices qui se déplacent dans une séquence pour résoudre des problèmes en un seul passage — transformant de nombreuses solutions par force brute O(n²) en **O(n)**.

## L'idée

Gardez deux pointeurs (souvent aux extrémités, ou un lent et un rapide) et déplacez-les en fonction d'une condition, réduisant le travail sans rescanner.

## Exemple : trouver une paire qui somme à une cible dans un tableau trié

```python
def two_sum_sorted(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:
            return (lo, hi)       # found the pair
        elif s < target:
            lo += 1               # need a bigger sum
        else:
            hi -= 1               # need a smaller sum
    return None

two_sum_sorted([1, 3, 4, 6, 9], 10)   # -> (1, 3) for 4 + 6
```

## Complexité

- **Temps :** O(n). **Espace :** O(1).

## Quand l'utiliser / pièges

Parfait pour les **tableaux triés**, les vérifications de palindromes, l'inversion et la suppression des doublons sur place. Le tableau doit souvent être trié pour la variante des pointeurs convergents. Attention aux limites des pointeurs et à la condition de boucle (`lo < hi`).

## Pourquoi c'est important

Les deux pointeurs constituent l'un des modèles d'interview les plus puissants : il réduit les boucles imbriquées à un balayage linéaire propre.

Cela vous enseigne à exploiter la structure (comme la présence de tri) au lieu de la force brute.

La même idée alimente la fusion, le partitionnement et l'étape de fusion du tri par fusion.