Fenster zählen, die eine Regel erfüllen
Der Trick: höchstens K minus höchstens (K-1)
Fenster zählen, die eine Regel erfüllen ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 4 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Zählen statt messen
Manchmal müssen Sie Teilarrays zählen, die eine Regel erfüllen, statt das längste zu finden. Ein kleiner Trick macht daraus eine einfache Aufgabe für das gleitende Fenster. 🔢
Die Herausforderung mit genau K
Teilarrays mit genau K Vorkommen einer Eigenschaft direkt zu zählen, ist unhandlich. Die Grenze wechselt ständig, wodurch ein einzelnes klares Fenster schwierig wird.
Die Umformulierung auf höchstens
Teilarrays mit höchstens K Vorkommen zu zählen, ist mit einem Fenster deutlich einfacher. Wenn Sie right erweitern, ergibt jeder gültige Start ein gezähltes Teilarray.
Der Subtraktionstrick
Genau K entspricht atMost(K) minus atMost(K - 1). Zwei einfache Zählungen ergeben zusammen die eigentlich gesuchte, schwierigere Anzahl.
answer = at_most(k) - at_most(k - 1)Die Hilfsfunktion erstellen
Schreiben Sie eine Funktion, die Teilarrays mit höchstens k Vorkommen zählt. Sie verschiebt ein Fenster und verkleinert es, sobald die Anzahl k überschreitet.
def at_most(k):
left = 0
total = 0Bei einer Verletzung verkleinern
Erweitern Sie right und aktualisieren Sie das Fenster. Solange es mehr als k enthält, verschieben Sie left nach vorne, um es wieder in den zulässigen Bereich zu bringen.
while count > k:
# remove a[left]
left += 1Die Anzahl der Fenster addieren
Nachdem Sie das Fenster korrigiert haben, ist jedes bei right endende Teilarray mit einem Start ab left gültig. Addieren Sie right minus left plus eins.
total += right - left + 1Warum diese Anzahl funktioniert
Für ein festes right sind left, left+1 bis einschließlich right die gültigen Startpositionen. Das sind genau right - left + 1 Teilarrays, die alle höchstens k Vorkommen enthalten.
Die beiden Aufrufe kombinieren
Führen Sie die Hilfsfunktion zweimal aus und subtrahieren Sie die Ergebnisse. Jeder Aufruf benötigt O(n), daher bleibt auch die vollständige Zählung für genau K linear.
return at_most(k) - at_most(k - 1)Den Randfall absichern
Wenn k null ist, würde atMost(k - 1) den Wert minus eins verwenden. Behandeln Sie diesen Fall gesondert, damit die Hilfsfunktion weiterhin sinnvoll null zurückgibt.
Wo dieses Muster anwendbar ist
Die Idee at-most minus at-most eignet sich zum Zählen von Teilarrays mit genau K verschiedenen Werten, K ungeraden Zahlen oder jeder anderen monotonen Fenstereigenschaft.
Kurzer Check
Sie möchten Teilarrays mit genau K verschiedenen Elementen zählen.
Zusammenfassung
Genau K zu zählen bedeutet einfach atMost(K) minus atMost(K - 1). Jede Hilfsfunktion verschiebt ein Fenster in O(n), sodass die gesamte Zählung linear bleibt. ✅
Häufig gestellte Fragen
Ist die Lektion „Fenster zählen, die eine Regel erfüllen“ kostenlos?
Ja — der vollständige Text von „Fenster zählen, die eine Regel erfüllen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Fenster zählen, die eine Regel erfüllen“?
Der Trick: höchstens K minus höchstens (K-1) Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 4 von 4.
Wie lange dauert die Lektion „Fenster zählen, die eine Regel erfüllen“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Summen in Fenstern fester Größe
- Variables Fenster mit zwei Zeigern
- Längster Teilstring ohne Wiederholungen
- Fenster zählen, die eine Regel erfüllen