Метод скользящего окна

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
        
        

2

Задача

Модуль 1: Python Core, 19 уровень, 2 лекция

Недоступна

Подмассив

Подмассив

Открыть

2

Задача

Модуль 1: Python Core, 19 уровень, 2 лекция

Недоступна

Большой подмассив

Большой подмассив

Открыть