Fenêtre variable avec deux pointeurs
Agrandir et réduire la fenêtre pour satisfaire une condition
Fenêtre variable avec deux pointeurs est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 2 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.
Quand la fenêtre respire
Dans certains problèmes, la longueur de la fenêtre n'est pas fixée. La fenêtre grandit et rétrécit plutôt afin de respecter une condition, comme le fait de maintenir une somme sous une limite.
Deux pointeurs, une fenêtre
Conservez deux indices, gauche et droite, qui indiquent les bords de la fenêtre. Le pointeur droit l'élargit tandis que le pointeur gauche reste en arrière pour la réduire si nécessaire.
left = 0
window = 0Étendre vers la droite
Parcourez chaque élément vers la droite et incluez-le dans la fenêtre. Mettez à jour l'état cumulé, par exemple en ajoutant la nouvelle valeur à une somme.
for right in range(n):
window += a[right]Réduire quand c'est nécessaire
Tant que la fenêtre ne respecte pas la règle, avancez la borne gauche vers la droite et retirez cet élément. Vous rétablissez ainsi la condition sans revenir en arrière.
while window > limit:
window -= a[left]
left += 1Lire la fenêtre valide
Une fois la boucle interne terminée, la fenêtre allant de gauche à droite est valide. Sa longueur vaut droite moins gauche plus un et elle est prête à être utilisée.
length = right - left + 1Enregistrer votre meilleur résultat
Mettez à jour votre réponse avec cette fenêtre valide, souvent la fenêtre la plus longue rencontrée. Faites-le à chaque itération pour ne rien manquer.
best = max(best, right - left + 1)Pourquoi c'est linéaire
Chaque pointeur avance uniquement vers l'avant, sans jamais revenir en arrière. Gauche et droite avancent ensemble d'au plus n positions, donc le parcours complet est en O(n).
La condition de monotonie
Cette méthode fonctionne lorsque l'extension de la fenêtre rend la condition plus difficile à satisfaire. C'est ce comportement monotone qui permet à gauche de ne jamais revenir en arrière.
Plus longue ou plus courte
Pour trouver la fenêtre valide la plus courte, réduisez-la tant que la règle est respectée et enregistrez le résultat avant de sortir de la boucle. La mécanique des pointeurs reste la même.
while window >= target:
best = min(best, right - left + 1)
window -= a[left]
left += 1Attention aux fenêtres vides
Si la réduction peut vider la fenêtre, empêchez gauche de dépasser droite. Vérifiez également qu'une réponse a réellement été trouvée avant de la retourner.
Reconnaître le modèle
Utilisez une fenêtre variable lorsqu'un problème demande la portion contiguë la plus longue ou la plus courte respectant une condition sur ses éléments.
Vérification rapide
Vous parcourez un tableau de taille n avec une fenêtre variable à deux pointeurs.
Récapitulatif
Avancez droite pour inclure les éléments, réduisez gauche tant que la règle n'est plus respectée, puis enregistrez chaque fenêtre valide. Des pointeurs qui avancent uniquement vers l'avant garantissent une complexité en O(n). ✅
Questions Fréquemment Posées
La leçon « Fenêtre variable avec deux pointeurs » est-elle gratuite ?
Oui — le texte complet de « Fenêtre variable avec deux pointeurs » 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 « Fenêtre variable avec deux pointeurs » ?
Agrandir et réduire la fenêtre pour satisfaire une condition 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 2 sur 4.
Combien de temps prend la leçon « Fenêtre variable avec deux pointeurs » ?
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
- Sommes sur une fenêtre de taille fixe
- Fenêtre variable avec deux pointeurs
- Plus longue sous-chaîne sans répétitions
- Compter les fenêtres qui respectent une règle