Leçon 5 : tableaux et deux pointeurs

Imagine une étagère de livres collés les uns aux autres : tu veux le troisième ? Tu comptes trois et tu sautes directement dessus. C'est un tableau (array) — atteindre un élément par index est O(1). Aujourd'hui, on découvre une astuce sympa, les « deux pointeurs » (two pointers) : au lieu d'un seul

Les deux pointeurs, c'est comme deux personnes qui lisent une longue ligne depuis les deux bouts — l'une commence au début de la ligne et l'autre à la fin, et elles avancent l'une vers l'autre jusqu'à se rejoindre au milieu. On termine ainsi rapidement, au lieu que chacune lise seule toute la ligne.

deux pointeurs: Un pattern où deux index se déplacent sur un tableau (des extrémités vers l'intérieur, ou dans la même direction) pour résoudre un problème en un seul passage.
sur place (in-place): Modifier les données à l'intérieur de la structure existante sans en allouer une nouvelle — O(1) mémoire supplémentaire.
mémoire contiguë: Stocker les éléments les uns à côté des autres en mémoire, ce qui permet un accès par index en O(1) et un parcours favorable au cache.