Deux pointeurs sur un tableau trié
Déplacer les extrémités vers l’intérieur pour atteindre une cible
Deux pointeurs sur un tableau trié est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Pourquoi utiliser deux pointeurs
La technique des two-pointer parcourt un tableau avec deux indices au lieu de boucles imbriquées, transformant de nombreuses idées en O(n^2) en un seul parcours clair en O(n). 🎯
Trié est le mot magique
La version classique nécessite un tableau trié. L’ordre permet de raisonner : avancer vers la droite augmente la valeur, avancer vers la gauche la diminue, de sorte que chaque étape constitue une véritable décision.
Deux pointeurs aux extrémités
Placez un pointeur à l’extrémité gauche et l’autre à l’extrémité droite. Ils se font face et réduiront progressivement l’écart qui les sépare.
left = 0
right = len(a) - 1Rapprocher les extrémités
À chaque étape, déplacez exactement un pointeur vers l’intérieur. L’ordre du tableau vous indique quel côté rapprocher pour atteindre votre objectif.
La condition de la boucle
Continuez la boucle tant que left < right. Lorsqu’ils se rencontrent ou se croisent, toutes les paires utiles ont été vérifiées et vous pouvez vous arrêter.
while left < right:
# inspect a[left] and a[right]
passLire la somme actuelle
Considérez a[left] + a[right] comme votre candidat actuel. La comparaison avec une cible vous indique si vous devez obtenir ensuite une valeur plus grande ou plus petite.
total = a[left] + a[right]Trop petite : avancer à gauche
Si la somme est inférieure à la cible, vous devez obtenir davantage. Déplacez le pointeur gauche vers la droite, en direction des valeurs plus grandes, puisque le tableau est trié par ordre croissant.
if total < target:
left += 1Trop grande : avancer à droite
Si la somme est supérieure à la cible, vous devez obtenir moins. Déplacez le pointeur droit vers la gauche, en direction des valeurs plus petites, afin de réduire le total.
elif total > target:
right -= 1Chaque étape élimine du travail
Chaque déplacement élimine tout un ensemble de paires que vous n’avez pas besoin de tester. C’est pourquoi le parcours est linéaire et non quadratique.
Pourquoi la méthode reste correcte
Vous ne supprimez que les paires qui ne peuvent pas convenir : la bonne réponse n’est donc jamais ignorée. Cette garantie rend la méthode des deux pointeurs fiable dans les concours.
Au-delà des extrémités
La même idée permet de résoudre des variantes : inversion sur place, partitionnement et fusion. Une fois que vous maîtrisez le déplacement des pointeurs jusqu’à leur rencontre, ces techniques deviennent familières.
Vérification rapide
Vous parcourez un tableau trié depuis ses deux extrémités pour trouver une somme cible.
Récapitulatif
Deux pointeurs parcourent un tableau trié depuis ses deux extrémités et l’un d’eux avance vers l’intérieur à chaque étape, tant que left < right. Une méthode linéaire et correcte, à la base de nombreuses astuces. 🚀
Questions Fréquemment Posées
La leçon « Deux pointeurs sur un tableau trié » est-elle gratuite ?
Oui — le texte complet de « Deux pointeurs sur un tableau trié » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Deux pointeurs sur un tableau trié » ?
Déplacer les extrémités vers l’intérieur pour atteindre une cible Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.
Combien de temps prend la leçon « Deux pointeurs sur un tableau trié » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Deux pointeurs sur un tableau trié
- Trouver une paire d’une somme donnée
- Supprimer les doublons sur place
- Fusionner deux séquences triées