Compter les fenêtres qui respectent une règle
Astuce : au plus K moins au plus (K-1)
Compter les fenêtres qui respectent une règle est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 4 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.
Compter plutôt que mesurer
Il faut parfois compter les sous-tableaux qui respectent une règle, plutôt que trouver le plus long. Une petite astuce transforme ce problème en un simple parcours avec fenêtre glissante. 🔢
Le défi d'une quantité exacte de K
Compter directement les sous-tableaux contenant exactement K occurrences d'un élément est délicat. La limite change sans cesse, ce qui rend difficile la création d'une fenêtre unique et simple.
Reformuler avec au plus
Compter les sous-tableaux contenant au plus K éléments est bien plus simple avec une seule fenêtre. En étendant droite, chaque position de départ valide donne un sous-tableau à compter.
L'astuce de la soustraction
Exactement K équivaut à atMost(K) moins atMost(K - 1). Deux comptages simples se combinent pour obtenir celui, plus délicat, dont vous avez réellement besoin.
answer = at_most(k) - at_most(k - 1)Construire la fonction auxiliaire
Écrivez une fonction qui compte les sous-tableaux contenant au plus k éléments. Elle fait glisser une fenêtre et la réduit chaque fois que le compte dépasse k.
def at_most(k):
left = 0
total = 0Réduire en cas de violation
Étendez droite et mettez à jour la fenêtre. Tant qu'elle contient plus de k éléments, avancez gauche pour la ramener dans les limites.
while count > k:
# remove a[left]
left += 1Ajouter le nombre de fenêtres
Après avoir corrigé la fenêtre, chaque sous-tableau se terminant à droite et commençant à gauche ou plus loin est valide. Ajoutez droite moins gauche plus un.
total += right - left + 1Pourquoi ce comptage fonctionne
Pour une position droite fixée, les départs valides sont gauche, gauche+1, jusqu'à droite. Cela représente exactement droite - gauche + 1 sous-tableaux, qui respectent tous la contrainte d'au plus k éléments.
Combiner les deux appels
Exécutez deux fois la fonction auxiliaire, puis soustrayez. Chaque appel est en O(n), donc le comptage complet d'exactement K reste linéaire.
return at_most(k) - at_most(k - 1)Gérer le cas limite
Lorsque k vaut zéro, atMost(k - 1) utiliserait moins un. Gérez ce cas afin que la fonction auxiliaire retourne toujours un comptage nul cohérent.
Quand l'utiliser
L'idée au plus moins au plus convient pour compter les sous-tableaux contenant exactement K valeurs distinctes, K nombres impairs ou toute propriété monotone appliquée à une fenêtre.
Vérification rapide
Vous voulez compter les sous-tableaux contenant exactement K éléments distincts.
Récapitulatif
Compter exactement K revient simplement à calculer atMost(K) moins atMost(K - 1). Chaque fonction auxiliaire fait glisser une fenêtre en O(n), donc le comptage total reste linéaire. ✅
Questions Fréquemment Posées
La leçon « Compter les fenêtres qui respectent une règle » est-elle gratuite ?
Oui — le texte complet de « Compter les fenêtres qui respectent une règle » 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 « Compter les fenêtres qui respectent une règle » ?
Astuce : au plus K moins au plus (K-1) 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 4 sur 4.
Combien de temps prend la leçon « Compter les fenêtres qui respectent une règle » ?
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