Метод ковзаючого вікна

3.1 Визначення методу ковзаючого вікна.

Метод ковзаючого вікна (Sliding Window) — це техніка, що використовується для розв'язання задач на масивах або рядках, при якій фіксований підмасив (або підрядок) переміщується по даних з метою пошуку оптимального розв'язку. Це дозволяє обробляти елементи у вікні фіксованого розміру і динамічно змінювати вікно в залежності від умов задачі.

Ця техніка особливо корисна для задач, пов'язаних з послідовностями даних, таких як масиви або рядки, і допомагає зменшити часову складність у порівнянні з більш наївними підходами.

Основні принципи

• Ініціалізація вікна: Встановіть початок і кінець вікна на початкові позиції.
• Переміщення вікна: Послідовно переміщуйте межі вікна, додаючи елементи з одного боку і видаляючи елементи з іншого.
• Обробка вікна: На кожному кроці виконуйте необхідні обчислення для поточного вікна.

Часова та просторовая складність метода ковзаючого вікна

Часова складність:

• O(n) — у більшості випадків, так як вказівник або вікно переміщується по масиву лінійно, перевіряючи кожну можливу позицію вікна.

Просторова складність:

• O(1) — якщо використовується фіксована кількість додаткової пам'яті для зберігання поточних значень.
• O(k) — якщо необхідно зберігати елементи всередині поточного вікна розміром k.

3.2 Знаходження максимальної суми підмасиву.

Знаходження максимальної суми підмасиву фіксованого розміру

Задача:

Знайти підмасив фіксованого розміру k з максимальною сумою.

Розв'язок:

Використовуємо метод ковзаючого вікна для підтримки поточної суми підмасиву і оновлюємо максимальну суму по мірі переміщення вікна.

Часова складність: O(n).

Приклад коду на Python:

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 Пошук усіх анаграм підрядка в рядку

Задача:

Знайти всі анаграми заданого підрядка p у рядку s.

Розв'язок:

Використовуємо метод ковзаючого вікна для підтримки частотного словника символів поточного вікна і порівнюємо його з частотним словником підрядка.

Часова складність: O(n).

Приклад коду на Python:

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 Знаходження мінімального підмасиву

Знаходження мінімального підмасиву з сумою, що перевищує задане значення

Задача:

Знайти мінімальний підмасив з сумою елементів, що перевищує задане значення S.

Розв'язок:

Використовуємо метод ковзаючого вікна для розширення правої межі доти, поки сума не стане більшою за S, потім зсуваємо ліву межу для мінімізації довжини підмасиву.

Часова складність: O(n).

Приклад коду на Python:

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