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 Coding Interview Prep 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 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.
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 Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep 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 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 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 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
- 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łę