Okno przesuwne dla podciągów
Zaimplementują Państwo okno przesuwne o zmiennym rozmiarze, aby znaleźć najdłuższy podciąg bez powtarzających się znaków oraz najmniejsze okno zawierające wszystkie znaki docelowe.
Okno przesuwne dla podciągów to bezpłatna lekcja DSA 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 DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Koncepcja przesuwnego okna
Przesuwne okno przechowuje podtablicę (lub podłańcuch) między lewym a prawym wskaźnikiem. Zamiast ponownie obliczać właściwości każdej możliwej podtablicy od podstaw w czasie O(n²), okno rozszerza się w prawo przez dodanie jednego elementu i zmniejsza się od lewej przez usunięcie jednego elementu, utrzymując bieżący stan w czasie O(1) na krok. W rezultacie otrzymujemy algorytm O(n). Okno nazywa się „przesuwnym”, ponieważ przesuwa się do przodu przez tablicę i nie cofa się.
# Fixed-size window sum: O(n) after O(k) setup
def max_sum_window(nums, k):
window_sum = sum(nums[:k]) # initial window
best = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] # add new right
window_sum -= nums[i - k] # remove old left
best = max(best, window_sum)
return best
print(max_sum_window([2,1,5,1,3,2], 3)) # 9 ([5,1,3])Stały a zmienny rozmiar okna
Istnieją dwa warianty przesuwnego okna. W przypadku okna o stałym rozmiarze oba wskaźniki przesuwają się w tym samym tempie, a okno zawsze zawiera dokładnie k elementów. W przypadku okna o zmiennym rozmiarze prawy wskaźnik zachłannie rozszerza okno, a lewy zmniejsza je dopiero wtedy, gdy okno narusza ograniczenie. Okna o zmiennym rozmiarze rozwiązują problemy takie jak „najdłuższy podłańcuch bez powtarzających się znaków”, w których optymalny rozmiar okna nie jest z góry znany.
# Variable window: longest substring with at most k distinct chars
def longest_k_distinct(s, k):
from collections import defaultdict
freq = defaultdict(int)
left = 0
best = 0
for right in range(len(s)):
freq[s[right]] += 1
while len(freq) > k: # window invalid: shrink
freq[s[left]] -= 1
if freq[s[left]] == 0:
del freq[s[left]]
left += 1
best = max(best, right - left + 1)
return best
print(longest_k_distinct('eceba', 2)) # 3 ('ece')
print(longest_k_distinct('aa', 1)) # 2Najdłuższy podłańcuch bez powtórzeń
To najbardziej znany problem ze zmiennym przesuwnym oknem. Należy użyć zbioru do śledzenia znaków znajdujących się w bieżącym oknie. Proszę rozszerzać okno w prawo; po znalezieniu duplikatu należy zmniejszać je od lewej, aż duplikat zostanie usunięty. Szybsza wersja używa mapy haszującej przechowującej najnowszy indeks każdego znaku, dzięki czemu lewy wskaźnik może w jednym kroku przeskoczyć za duplikat, zamiast przesuwać się po trochu.
def length_of_longest_substring(s):
char_idx = {} # char -> last seen index
left = 0
best = 0
for right, c in enumerate(s):
if c in char_idx and char_idx[c] >= left:
left = char_idx[c] + 1 # jump past duplicate
char_idx[c] = right
best = max(best, right - left + 1)
return best
print(length_of_longest_substring('abcabcbb')) # 3 ('abc')
print(length_of_longest_substring('bbbbb')) # 1
print(length_of_longest_substring('pwwkew')) # 3 ('wke')Najkrótszy podłańcuch zawierający wzorzec
Dla łańcuchów s i t należy znaleźć najmniejsze okno w s zawierające wszystkie znaki t. Należy użyć dwóch map częstości: need (wymagane znaki) oraz have (znaki w bieżącym oknie spełniające wymaganie). Proszę śledzić, ile różnych znaków z t jest spełnionych (licznik formed). Należy rozszerzać okno w prawo, aby uwzględniać kolejne znaki; gdy obejmuje ono całe t, trzeba zmniejszać je od lewej, aby zminimalizować jego rozmiar. Czas działania wynosi O(|s| + |t|).
from collections import Counter
def min_window(s, t):
if not t or not s: return ''
need = Counter(t)
have = {}
formed = 0
required = len(need)
left = 0
best = float('inf'), 0, 0
for right, c in enumerate(s):
have[c] = have.get(c, 0) + 1
if c in need and have[c] == need[c]:
formed += 1
while formed == required:
if right - left + 1 < best[0]:
best = right - left + 1, left, right
have[s[left]] -= 1
if s[left] in need and have[s[left]] < need[s[left]]:
formed -= 1
left += 1
return s[best[1]:best[2]+1] if best[0] != float('inf') else ''
print(min_window('ADOBECODEBANC', 'ABC')) # 'BANC'Szablon przesuwnego okna
Większość problemów ze zmiennym przesuwnym oknem ma wspólny schemat: rozszerzyć okno w prawo, aby uwzględnić nowy znak, zaktualizować stan okna, sprawdzić jego poprawność, a jeśli jest niepoprawne, zmniejszać je od lewej, aż ponownie stanie się poprawne. Kluczowa obserwacja jest taka, że lewy wskaźnik przesuwa się wyłącznie do przodu — nigdy się nie cofa — dlatego łączny koszt wszystkich kroków zmniejszania wynosi O(n). Okno odwiedza każdy element najwyżej dwa razy: raz podczas dodawania i raz podczas usuwania.
def sliding_window_template(s, condition_check, update_state, remove_state):
"""
Generic sliding window skeleton.
Adapt condition_check, update_state, remove_state per problem.
"""
left = 0
state = {} # or whatever state you need
best = 0
for right in range(len(s)):
update_state(state, s[right]) # expand window
while not condition_check(state): # window invalid
remove_state(state, s[left]) # shrink window
left += 1
best = max(best, right - left + 1)
return bestPermutacja w łańcuchu znaków
Należy sprawdzić, czy dowolna permutacja wzorca p występuje jako podłańcuch s. Sprawdzenie permutacji jest równoważne znalezieniu okna o takiej samej częstości znaków jak p. Należy utrzymywać przesuwne okno zawierające dokładnie len(p) znaków i porównywać liczniki częstości. Porównywanie całych obiektów Counter w każdym kroku kosztuje O(26) (wartość stała dla małych liter alfabetu angielskiego), co daje łącznie O(n × 26) = O(n).
from collections import Counter
def check_inclusion(p, s):
if len(p) > len(s): return False
need = Counter(p)
window = Counter(s[:len(p)])
if need == window: return True
for right in range(len(p), len(s)):
left = right - len(p)
window[s[right]] += 1
window[s[left]] -= 1
if window[s[left]] == 0:
del window[s[left]]
if window == need:
return True
return False
print(check_inclusion('ab', 'eidbaooo')) # True ('ba')
print(check_inclusion('ab', 'eidboaoo')) # FalsePodłańcuchy będące anagramami: zliczanie wszystkich
Należy znaleźć wszystkie indeksy początkowe anagramów p w s. Jest to ta sama technika stałego okna co w przypadku permutacji w łańcuchu, jednak zamiast zwracać True po znalezieniu pierwszego dopasowania, zbieramy wszystkie pasujące pozycje. Rozmiar okna jest stały i wynosi len(p); przesuwamy je przez s i na każdym kroku porównujemy liczniki częstości.
from collections import Counter
def find_anagrams(s, p):
result = []
need = Counter(p)
k = len(p)
window = Counter(s[:k])
if window == need:
result.append(0)
for right in range(k, len(s)):
window[s[right]] += 1
left_char = s[right - k]
window[left_char] -= 1
if window[left_char] == 0:
del window[left_char]
if window == need:
result.append(right - k + 1)
return result
print(find_anagrams('cbaebabacd', 'abc')) # [0, 6]Najdłuższy podłańcuch z co najwyżej 2 różnymi znakami
Jest to wariant przesuwnego okna: należy znaleźć najdłuższy podłańcuch zawierający co najwyżej 2 różne znaki. Proszę utrzymywać mapę częstości znaków w bieżącym oknie. Gdy mapa zawiera więcej niż 2 wpisy, należy przesuwać lewy wskaźnik w prawo (zmniejszać częstość i usuwać wpis, gdy częstość wynosi zero), aż ograniczenie zostanie ponownie spełnione. Jest to szczególny przypadek problemu „co najwyżej k różnych znaków”, w którym k=2.
def longest_substring_two_distinct(s):
from collections import defaultdict
freq = defaultdict(int)
left = 0
best = 0
for right, c in enumerate(s):
freq[c] += 1
while len(freq) > 2:
freq[s[left]] -= 1
if freq[s[left]] == 0:
del freq[s[left]]
left += 1
best = max(best, right - left + 1)
return best
print(longest_substring_two_distinct('eceba')) # 3 ('ece')
print(longest_substring_two_distinct('ccaabbb')) # 5 ('aabbb')Maksimum w przesuwnym oknie
Należy znaleźć maksimum w każdym oknie o rozmiarze k. Sprawdzanie maksimum każdego okna metodą naiwną kosztuje O(n×k). Optymalne rozwiązanie używa monotonicznej kolejki dwustronnej indeksów: należy utrzymywać kolejkę w porządku malejącym, tak aby jej początek zawsze zawierał indeks maksimum bieżącego okna. Gdy indeksy opuszczają okno, należy usuwać je z początku, a gdy pojawia się większy element — usuwać indeksy z końca. Łączny czas działania wynosi O(n).
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # stores indices, decreasing values
result = []
for i, n in enumerate(nums):
# Remove indices outside window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Maintain decreasing order
while dq and nums[dq[-1]] < n:
dq.pop()
dq.append(i)
if i >= k - 1: # window is full
result.append(nums[dq[0]])
return result
print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]Kiedy używać przesuwnego okna
Warto sięgnąć po przesuwne okno, gdy występuje:
- podłańcuch lub podtablica z ograniczeniem (maksymalna długość, suma = k, co najwyżej k różnych znaków)
- okno o stałym rozmiarze z operacją agregującą (maksimum, suma, częstość)
- pytanie dotyczące spójnego zakresu (a nie dowolnych podzbiorów)
# Recognising sliding window problems:
# 1. Fixed window: 'maximum average of subarray of length k'
def max_avg(nums, k):
s = sum(nums[:k])
best = s
for i in range(k, len(nums)):
s += nums[i] - nums[i-k]
best = max(best, s)
return best / k
print(max_avg([1,12,-5,-6,50,3], 4)) # 12.75
# 2. Variable window: 'smallest subarray with sum >= target'
def min_sub_len(target, nums):
left = s = 0
best = float('inf')
for right, n in enumerate(nums):
s += n
while s >= target:
best = min(best, right - left + 1)
s -= nums[left]; left += 1
return 0 if best == float('inf') else best
print(min_sub_len(7, [2,3,1,2,4,3])) # 2Zliczanie poprawnych okien: co najwyżej K
Niektóre problemy wymagają policzenia liczby podtablic spełniających określony warunek. Przydatny sposób polega na zliczeniu podtablic zawierających co najwyżej k różnych znaków, a następnie odjęciu tej wartości, aby uzyskać wynik dla dokładnie k: exactly(k) = at_most(k) - at_most(k-1). Każde wywołanie at_most ma złożoność O(n), więc łączna złożoność wynosi O(n). Funkcja at_most zlicza okna, w których liczba różnych znaków nie przekracza k, sumując right - left + 1 (wszystkie poprawne pozycje lewego końca dla każdego prawego końca).
from collections import defaultdict
def subarrays_at_most_k(s, k):
freq = defaultdict(int)
left = 0
count = 0
for right, c in enumerate(s):
freq[c] += 1
while len(freq) > k:
freq[s[left]] -= 1
if freq[s[left]] == 0: del freq[s[left]]
left += 1
count += right - left + 1 # all valid windows ending at right
return count
def subarrays_exactly_k(s, k):
return subarrays_at_most_k(s, k) - subarrays_at_most_k(s, k-1)
print(subarrays_exactly_k('araaci', 2)) # 9Szybki test
Proszę sprawdzić znajomość koncepcji przedstawionych w tej lekcji w ramach Data Structures & Algorithms — Coding Interview Prep.
Podsumowanie lekcji
W tej lekcji poznali Państwo: przesuwne okno eliminuje O(n²), utrzymując bieżący stan okna aktualizowany w czasie O(1), gdy elementy wchodzą do okna i z niego wychodzą, okna o stałym rozmiarze przesuwają oba wskaźniki w tym samym tempie, a okna o zmiennym rozmiarze zachłannie rozszerzają się w prawo i zmniejszają w lewo dopiero po naruszeniu ograniczenia, oraz problemy najkrótszego podłańcucha zawierającego wzorzec i permutacji w łańcuchu używają stanu okna opartego na mapie częstości oraz licznika śledzącego, ile wymaganych znaków jest aktualnie spełnionych. W następnej lekcji omówimy anagramy i mapy częstości znaków.
Często zadawane pytania
Czy lekcja „Okno przesuwne dla podciągów” jest bezpłatna?
Tak — pełny tekst „Okno przesuwne dla podciągów” 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 DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Okno przesuwne dla podciągów”?
Zaimplementują Państwo okno przesuwne o zmiennym rozmiarze, aby znaleźć najdłuższy podciąg bez powtarzających się znaków oraz najmniejsze okno zawierające wszystkie znaki docelowe. Ćwiczysz DSA 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ąć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA 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 „Okno przesuwne dla podciągów”?
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 DSA Interview Prep?
Tak. Każda lekcja DSA 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
- Python String API na rozmowach rekrutacyjnych
- Okno przesuwne dla podciągów
- Anagramy i mapy częstotliwości znaków
- Kodowanie ciągów, odwracanie i palindromy