Tableaux et chaînes : les bases

Un tableau stocke des éléments dans des emplacements contigus en mémoire. Ça permet un accès par index en O(1) : `arr[i]` ne dépend pas de la taille du tableau. C'est le principal avantage du tableau face à une liste chaînée.

En revanche, insérer ou supprimer au milieu d'un tableau coûte O(n) : il faut décaler tous les éléments suivants. Ajouter/retirer à la fin est en général O(1) amorti (sauf redimensionnement).

Les chaînes de caractères se comportent comme des tableaux de caractères. Dans la plupart des langages utilisés en entretien (JavaScript, Python, Java), elles sont immuables : chaque concaténation crée une nouvelle chaîne. Enchaîner des concaténations dans une boucle peut donc coûter O(n²) au lieu de O(n) — préfère un tableau de caractères ou un buffer, puis joins-le à la fin.

Deux patterns à connaître dès maintenant, qu'on approfondira en Phase 1 : le two-pointers (deux index qui se déplacent dans le tableau, utile pour les tableaux triés ou les palindromes) et le sliding window (une fenêtre de taille variable ou fixe qu'on fait glisser, utile pour les sous-tableaux/sous-chaînes contigus).

Réflexe utile : avant de coder, demande-toi si le tableau est trié (ça ouvre la porte à la recherche binaire ou aux deux pointeurs) et quelles sont les contraintes de taille (`n` jusqu'à 10⁵ ? 10⁹ ?) — ça te dit quelle complexité est acceptable.

Vidéo

Quiz