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 Competitive Programming Academy 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 Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy 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 = windowPrzesunię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 / kObsł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 NoneKiedy 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 Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy 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 Competitive Programming Academy 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ąć Competitive Programming Academy?
Nie wymagamy żadnego doświadczenia. Competitive Programming Academy 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 Competitive Programming Academy?
Tak. Każda lekcja Competitive Programming Academy 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
- Sumy okien o stałym rozmiarze
- Zmienny zakres okna z dwoma wskaźnikami
- Najdłuższy podnapis bez powtórzeń
- Zliczanie okien spełniających regułę