Motif 2 — Deux pointeurs

L'idée, en une ligne

Placez un marqueur à chaque extrémité d'une liste et faites-les avancer l'un vers l'autre, en une seule passe au lieu d'une boucle dans une boucle. C'est le motif deux pointeurs.

Comment le repérer

Le grand signal est une liste triée, ou une chaîne que vous comparez de l'avant et de l'arrière en même temps. La tâche demande généralement l'une de ces choses :

• une paire dont la somme atteint une cible — comme deux temps de réponse qui tiennent dans un budget SLA
• une vérification de palindrome — se lit pareil à l'endroit et à l'envers
• inverser une liste sur place — sans copie, sans slicing

Le mouvement, étape par étape

1. Placez left au premier indice et right au dernier.
2. Additionnez les deux valeurs et comparez à la cible.
3. Total trop petit ? Avancez left d'un cran pour gagner de la valeur.
4. Total trop grand ? Reculez right d'un cran pour perdre de la valeur.
5. Égal ? Vous avez trouvé votre paire. Continuez tant que left est en dessous de right.

Voyez-le à l'œuvre

# Two response times that add up to a target budget (sorted input)
def has_pair(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return (nums[left], nums[right])
        if total < target:
            left += 1        # need more -> move left up
        else:
            right -= 1       # too much -> move right down
    return None

print(has_pair([1, 2, 4, 5, 9], 9))   # (4, 5)

Lisez-le de haut en bas : commencez aux deux extrémités, poussez l'extrémité dont vous avez besoin, et arrêtez dès que les deux marqueurs se rencontrent. Une vérification de palindrome a exactement la même forme — comparez les deux extrémités, avancez vers l'intérieur, et échouez à l'instant où elles diffèrent.

# Palindrome check: compare the ends, step inward
def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left, right = left + 1, right - 1
    return True

print(is_palindrome("abccba"))   # True

Avancé — pourquoi c'est rapide, et pourquoi le tri compte

Parce que la liste est triée, elle a une direction : bouger un pointeur ne saute pas juste un élément, il élimine toute une plage que vous n'aurez plus jamais à vérifier. C'est ce qui transforme une double boucle lente en une seule passe.

Basé sur le tutoriel « Two Pointers Technique » de GeeksforGeeks