Deux pointeurs et fenêtre glissante
Pourquoi un parcours intelligent est important
Imaginez une IA surveillant un flux vidéo en direct pour détecter des activités suspectes. Elle ne peut pas revisionner l'intégralité de l'enregistrement chaque seconde - elle doit faire glisser une fenêtre d'attention sur le flux, en conservant juste assez de contexte. C'est exactement ce que font les patterns two pointers et sliding window pour les données séquentielles.
Ces deux techniques transforment des parcours brute-force en O(n²) en élégants parcours en O(n).
La technique Two Pointers
Placez deux références dans une séquence et déplacez-les selon une règle. Il existe deux variantes principales.
Pointeurs convergents
Placez un pointeur à chaque extrémité et déplacez-les vers l'intérieur. Idéal pour les données triées.
Problème classique - Pair Sum : Étant donné un tableau trié, trouvez deux nombres dont la somme correspond à une cible.
function pairSum(arr, target):
left = 0
right = arr.length - 1
while left < right:
sum = arr[left] + arr[right]
if sum == target: return (left, right)
if sum < target: left += 1
else: right -= 1
return null
Comme le tableau est trié, déplacer left vers la droite augmente la somme, et déplacer right vers la gauche la diminue - garantissant qu'aucune paire valide n'est manquée.
Pointeurs dans la même direction
Les deux pointeurs avancent, mais à des vitesses différentes. Utile pour le partitionnement ou la détection de cycles.
Exemple - Supprimer les doublons en place : Un pointeur lent marque la position d'écriture ; un pointeur rapide parcourt en avance.
function removeDuplicates(arr):
slow = 0
for fast in 1..arr.length - 1:
if arr[fast] != arr[slow]:
slow += 1
arr[slow] = arr[fast]
return slow + 1
Discussion
Sign in to join the discussion