Zmienny zakres okna z dwoma wskaźnikami
Rozszerzanie i zmniejszanie zakresu do spełnienia warunku
Zmienny zakres okna z dwoma wskaźnikami to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 2 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.
Gdy okno zmienia rozmiar
W niektórych zadaniach długość okna nie jest ustalona. Zamiast tego okno zwiększa się i zmniejsza, aby zachować prawdziwość warunku, na przykład aby suma nie przekroczyła limitu.
Dwa wskaźniki, jedno okno
Należy przechowywać dwa indeksy, left i right, wyznaczające krawędzie okna. Wskaźnik right rozszerza okno, a left pozostaje z tyłu i w razie potrzeby je zmniejsza.
left = 0
window = 0Rozszerzanie w prawo
Należy przejść w prawo przez każdy element i włączyć go do okna. Trzeba przy tym aktualizować stan narastający, na przykład dodając nową wartość do sumy.
for right in range(n):
window += a[right]Zmniejszanie w razie potrzeby
Gdy okno narusza regułę, należy przesuwać left w prawo i usuwać wskazywane elementy. Przywraca to spełnienie warunku bez cofania się.
while window > limit:
window -= a[left]
left += 1Odczyt poprawnego okna
Po zakończeniu pętli wewnętrznej okno od left do right jest poprawne. Jego długość wynosi right minus left plus jeden i można od razu jej użyć.
length = right - left + 1Zapisywanie najlepszego wyniku
Należy zaktualizować wynik na podstawie tego poprawnego okna, często wybierając najdłuższe dotychczas znalezione. Trzeba robić to w każdej iteracji, aby niczego nie pominąć.
best = max(best, right - left + 1)Dlaczego czas jest liniowy
Każdy wskaźnik porusza się wyłącznie do przodu i nigdy się nie cofa. Wskaźniki left i right wykonują łącznie najwyżej n kroków, więc całe przejście ma koszt O(n).
Wymóg monotoniczności
To rozwiązanie działa, gdy rozszerzanie okna sprawia, że spełnienie warunku staje się tylko trudniejsze. Ta monotoniczność pozwala wskaźnikowi left nigdy się nie cofać.
Najdłuższe a najkrótsze
Aby znaleźć najkrótsze poprawne okno, należy zmniejszać je, dopóki reguła jest spełniona, i zapisać wynik przed jej naruszeniem. Mechanika wskaźników pozostaje taka sama.
while window >= target:
best = min(best, right - left + 1)
window -= a[left]
left += 1Uwaga na puste okna
Jeśli zmniejszanie może opróżnić okno, należy zabezpieczyć się przed sytuacją, w której left przechodzi za right. Trzeba również potwierdzić, że rzeczywiście znaleziono wynik, zanim zostanie on zwrócony.
Rozpoznawanie schematu
Po okno o zmiennej długości należy sięgnąć, gdy zadanie wymaga znalezienia najdłuższego lub najkrótszego spójnego fragmentu spełniającego warunek dotyczący jego elementów.
Szybkie sprawdzenie
Wykonują Państwo przejście po tablicy rozmiaru n za pomocą okna o zmiennej długości i dwóch wskaźników.
Podsumowanie
Należy przesuwać right, aby dołączać elementy, zmniejszać okno wskaźnikiem left, gdy reguła przestaje być spełniona, oraz zapisywać każde poprawne okno. Wskaźniki poruszające się wyłącznie do przodu zapewniają koszt O(n). ✅
Często zadawane pytania
Czy lekcja „Zmienny zakres okna z dwoma wskaźnikami” jest bezpłatna?
Tak — pełny tekst „Zmienny zakres okna z dwoma wskaźnikami” 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 „Zmienny zakres okna z dwoma wskaźnikami”?
Rozszerzanie i zmniejszanie zakresu do spełnienia warunku Ć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 2 z 4.
Ile czasu zajmuje lekcja „Zmienny zakres okna z dwoma wskaźnikami”?
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łę