0Pricing
Coding Interview Prep · Lekcja

Sumy okien o stałym rozmiarze

Przesuwanie okna długości k w O(n)

Sumy okien o stałym rozmiarze to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 1 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Problem powtarzających się sum

Wiele zadań wymaga obliczenia sumy każdego bloku k kolejnych elementów. Ponowne obliczanie sumy każdego bloku od początku jest nieefektywne — można zrobić to lepiej. 🪟

Najpierw naiwny sposób

Naiwne podejście polega na osobnym zsumowaniu każdego okna o długości k. Powoduje to wielokrotne wykonywanie tej samej pracy i ma koszt O(n razy k), co jest zbyt wolne dla dużych danych wejściowych.

for i in range(n - k + 1):
    s = sum(a[i:i + k])

Kluczowa obserwacja

Sąsiednie okna niemal całkowicie na siebie nachodzą. Przesunięcie o jeden krok w prawo usuwa tylko skrajny element z lewej i dodaje jeden nowy element z prawej.

Utworzenie pierwszego okna

Najpierw należy jednokrotnie zsumować pierwsze k elementów. Ta pojedyncza suma będzie podstawą aktualizowaną przy każdym kolejnym przesunięciu okna.

window = sum(a[:k])
best = window

Przesunięcie o jeden krok

Aby przesunąć okno, należy dodać element, który do niego wchodzi, i odjąć element, który je opuszcza. Dzięki temu każdy krok wymaga stałej pracy O(1).

for i in range(k, n):
    window += a[i] - a[i - k]

Śledzenie wyniku

Po każdym przesunięciu należy aktualizować potrzebną wartość, na przykład maksymalną dotychczas napotkaną sumę okna. Wartość okna jest zawsze natychmiast dostępna.

    best = max(best, window)

Łączny koszt jest liniowy

Każdy element jest odwiedzany raz podczas dodawania i jeszcze raz podczas usuwania, więc całe przejście ma koszt O(n). Bez problemu obsługuje to duże ograniczenia.

Uwaga na indeksy

Element opuszczający okno to a[i - k], a nie a[i - 1]. Poprawne ustalenie tego przesunięcia jest najczęstszym błędem w algorytmach ze stałym oknem.

Średnie bez dodatkowego kosztu

Potrzebne jest maksimum średniej okna zamiast sumy? Wystarczy podzielić śledzoną sumę okna przez k. Logika przesuwania nie zmienia się wcale.

avg = window / k

Obsługa małych tablic

Jeśli tablica jest krótsza niż k, nie istnieje żadne pełne okno. Należy wcześniej porównać len(a) z k i od razu zwrócić wynik, aby uniknąć błędu indeksu.

if n < k:
    return None

Kiedy pasują stałe okna

Ten schemat należy stosować, gdy długość okna jest stała, a wartości można tanio łączyć, na przykład obliczając sumy, zliczenia lub proste statystyki narastające.

Szybkie sprawdzenie

Przesuwają Państwo okno rozmiaru k o jeden krok w prawo po tablicy.

Podsumowanie

Należy raz utworzyć pierwsze okno, a następnie przy każdym kroku dodawać i odejmować elementy, aby przesuwać je w czasie O(1). Całe przejście po oknie o stałym rozmiarze działa w czasie liniowym. ✅

Często zadawane pytania

Czy lekcja „Sumy okien o stałym rozmiarze” jest bezpłatna?

Tak — pełny tekst „Sumy okien o stałym rozmiarze” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Co nauczysz się w „Sumy okien o stałym rozmiarze”?

Przesuwanie okna długości k w O(n) Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?

Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 1 z 4.

Ile czasu zajmuje lekcja „Sumy okien o stałym rozmiarze”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?

Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

  1. Sumy okien o stałym rozmiarze
  2. Zmienny zakres okna z dwoma wskaźnikami
  3. Najdłuższy podnapis bez powtórzeń
  4. Zliczanie okien spełniających regułę
← Powrót do Coding Interview Prep