Sommes sur une fenêtre de taille fixe
Faire glisser une fenêtre de longueur k en O(n)
Sommes sur une fenêtre de taille fixe 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.
Le problème de la somme répétée
De nombreuses tâches demandent la somme de chaque bloc de k éléments consécutifs. Recalculer chaque bloc depuis zéro est coûteux, et vous pouvez faire mieux. 🪟
D'abord, la méthode lente
L'idée naïve consiste à additionner séparément chaque fenêtre de longueur k. Cela répète des opérations et coûte O(n fois k), ce qui est trop lent pour des entrées volumineuses.
for i in range(n - k + 1):
s = sum(a[i:i + k])L'idée clé
Les fenêtres voisines se chevauchent presque entièrement. Avancer d'une position vers la droite consiste seulement à retirer l'élément le plus à gauche et à ajouter un nouvel élément à droite.
Initialiser la première fenêtre
Commencez par additionner une seule fois les k premiers éléments. Cette somme initiale sera mise à jour au fur et à mesure que la fenêtre avance.
window = sum(a[:k])
best = windowAvancer d'une position
Pour déplacer la fenêtre, ajoutez l'élément entrant et soustrayez celui qui sort. Chaque étape nécessite ainsi un travail constant en O(1).
for i in range(k, n):
window += a[i] - a[i - k]Suivre votre résultat
Après chaque déplacement, mettez à jour ce dont vous avez besoin, par exemple la somme maximale d'une fenêtre rencontrée jusque-là. La valeur de la fenêtre est ainsi toujours disponible instantanément.
best = max(best, window)Un coût total linéaire
Vous parcourez chaque élément pour l'ajouter, puis une seconde fois pour le retirer : le parcours complet est donc en O(n). Il respecte ainsi facilement les grandes contraintes.
Attention aux indices
L'élément qui quitte la fenêtre est a[i - k], et non a[i - 1]. Bien gérer ce décalage est l'erreur la plus courante avec une fenêtre de taille fixe.
Les moyennes sans effort supplémentaire
Vous avez besoin de la fenêtre dont la moyenne est maximale plutôt que de sa somme ? Divisez simplement la somme suivie de la fenêtre par k. La logique de la fenêtre glissante ne change pas.
avg = window / kGérer les petits tableaux
Si le tableau est plus court que k, aucune fenêtre complète n'existe. Comparez len(a) à k dès le début et retournez immédiatement pour éviter une erreur d'indice.
if n < k:
return NoneQuand les fenêtres fixes conviennent
Utilisez ce modèle lorsque la longueur est fixe et que vous combinez les valeurs à peu de frais, par exemple pour des sommes, des comptages ou de simples statistiques cumulées.
Vérification rapide
Vous faites glisser une fenêtre de taille k d'une position vers la droite à travers un tableau.
Récapitulatif
Initialisez une fois la première fenêtre, puis ajoutez et soustrayez à chaque étape pour la déplacer en O(1). Le parcours complet d'une fenêtre de taille fixe s'effectue en temps linéaire. ✅
Questions Fréquemment Posées
La leçon « Sommes sur une fenêtre de taille fixe » est-elle gratuite ?
Oui — le texte complet de « Sommes sur une fenêtre de taille fixe » 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 « Sommes sur une fenêtre de taille fixe » ?
Faire glisser une fenêtre de longueur k en O(n) 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 « Sommes sur une fenêtre de taille fixe » ?
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