Metoda przesuwającego się okna

3.1 Definicja metody przesuwającego się okna.

Metoda przesuwającego się okna (Sliding Window) — to technika, wykorzystywana do rozwiązywania zadań na tablicach lub łańcuchach znaków, w której stały podzbiór (lub podciąg) przesuwa się po danych w celu znalezienia optymalnego rozwiązania. Pozwala to przetwarzać elementy w oknie o stałym rozmiarze i dynamicznie zmieniać okno w zależności od warunków zadania.

Ta technika jest szczególnie użyteczna przy zadaniach związanych z sekwencjami danych, takich jak tablice czy łańcuchy znaków, i pomaga zmniejszyć złożoność czasową w porównaniu z bardziej naiwnymi podejściami.

Podstawowe zasady

• Inicjalizacja okna: Ustal początek i koniec okna na początkowych pozycjach.
• Przesuwanie okna: Sukcesywnie przesuwaj granice okna, dodając elementy z jednej strony i usuwając elementy z drugiej.
• Przetwarzanie okna: Na każdym kroku wykonuj konieczne obliczenia dla bieżącego okna.

Złożoność czasowa i przestrzenna metody przesuwającego się okna

Złożoność czasowa:

• O(n) — w większości przypadków, ponieważ wskaźnik lub okno przesuwa się po tablicy liniowo, sprawdzając każdą możliwą pozycję okna.

Złożoność przestrzenna:

• O(1) — jeśli używane jest stałe dodatkowe miejsce w pamięci do przechowywania bieżących wartości.
• O(k) — jeśli konieczne jest przechowywanie elementów wewnątrz bieżącego okna o rozmiarze k.

3.2 Znalezienie maksymalnej sumy podtablicy.

Znalezienie maksymalnej sumy podtablicy o stałym rozmiarze

Zadanie:

Znajdź podtablicę o stałym rozmiarze k z maksymalną sumą.

Rozwiązanie:

Używamy metody przesuwającego się okna do utrzymania bieżącej sumy podtablicy i aktualizujemy maksymalną sumę w miarę przesuwania się okna.

Złożoność czasowa: O(n).

Przykład kodu w Pythonie:

def max_sum_subarray(arr, k):
    n = len(arr)
    if n < k:
        return -1
            
    window_sum = sum(arr[:k])
    max_sum = window_sum
            
    for i in range(n - k):
        window_sum = window_sum - arr[i] + arr[i + k]
        max_sum = max(max_sum, window_sum)
            
    return max_sum
        
        

3.3 Wyszukiwanie wszystkich anagramów podciągu w łańcuchu

Zadanie:

Znajdź wszystkie anagramy danego podciągu p w łańcuchu s.

Rozwiązanie:

Używamy metody przesuwającego się okna do utrzymania słownika częstotliwości znaków w bieżącym oknie i porównujemy go ze słownikiem częstotliwości podciągu.

Złożoność czasowa: O(n).

Przykład kodu w Pythonie:

from collections import Counter

def find_anagrams(s, p):
    p_count = Counter(p)
    s_count = Counter()
                
    result = []
    k = len(p)
                
    for i in range(len(s)):
        s_count[s[i]] += 1
        
        if i >= k:
            if s_count[s[i - k]] == 1:
                del s_count[s[i - k]]
            else:
                s_count[s[i - k]] -= 1
                            
        if s_count == p_count:
            result.append(i - k + 1)

    return result
        

3.4 Znalezienie minimalnej podtablicy

Znalezienie minimalnej podtablicy z sumą przekraczającą zadana wartość

Zadanie:

Znajdź minimalną podtablicę z sumą elementów przekraczającą zadaną wartość S.

Rozwiązanie:

Używamy metody przesuwającego się okna do rozszerzenia prawej granicy dopóki suma nie przekroczy S, następnie przesuwamy lewą granicę w celu minimalizacji długości podtablicy.

Złożoność czasowa: O(n).

Przykład kodu w Pythonie:

def min_subarray_len(S, arr):
    n = len(arr)
    min_len = float('inf')
    current_sum = 0
    left = 0
            
    for right in range(n):
        current_sum += arr[right]
                
        while current_sum >= S:
            min_len = min(min_len, right - left + 1)
            current_sum -= arr[left]
            left += 1
            
    return 0 if min_len == float('inf') else min_len