Two pointers : deux index au lieu de deux boucles

Deux index qui parcourent la structure ramènent souvent un O(n²) à O(n).

Chaque élément n'est visité qu'un nombre constant de fois. Deux variantes :

• Extrémités qui se rapprochent : tableau trié, palindrome, paire de somme donnée.
• Même sens, vitesses différentes : suppression de doublons en place, cycle dans une liste chaînée (lent/rapide).

Two Sum II : tableau trié#

Si la somme est trop grande, on recule le pointeur droit ; trop petite, on avance le gauche.

function twoSumSorted(nums: number[], target: number): [number, number] | null {
  let left = 0;
  let right = nums.length - 1;
  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) return [left, right];
    if (sum < target) left++;
    else right--;
  }
  return null;                                      // O(n) temps, O(1) espace
}

Palindrome#

function isPalindrome(s: string): boolean {
  let i = 0;
  let j = s.length - 1;
  while (i < j) {
    if (s[i] !== s[j]) return false;
    i++;
    j--;
  }
  return true;
}

Piège : la variante « extrémités » exige un tableau trié. Sur un tableau non trié, soit on trie d'abord (O(n log n)), soit on utilise un hashmap si l'ordre des éléments compte.

Pour aller plus loin#

• NeetCode — Two Pointers (playlist) — NeetCode