Когда дело доходит до решения проблем с алгоритмами, есть несколько чрезвычайно полезных шаблонов (шаблон алгоритма или парадигма алгоритма — это метод, стратегия или техника решения проблемы), которые сделают нашу жизнь намного проще. «Скользящее окно» — распространенный шаблон решения задач в информатике. Чаще всего он используется для массивов и строк. Основной принцип заключается в том, чтобы создать «окно», а затем проверить, удовлетворяют ли данные в окне условию вашей задачи, а также преобразовать два вложенных цикла в один цикл. В конце этой статьи вы найдете полезные ресурсы, которые помогут вам с этим шаблоном.

ключевые слова: найдите минимальное, максимальное, самое короткое или самое длинное.

Получить репозиторий этих примеров: https://github.com/LuisSalas94/Sliding-Window-Pattern-Article

Пример 01:

Постановка задачи

Для заданного массива найдите среднее значение всех подмассивов из «k» смежных элементов в нем.

Массив: [1, 3, 2, 6, -1, 4, 1, 8, 2], k = 5

Здесь нас просят найти среднее значение всех подмассивов из «5» смежных элементов в данном массиве. Давайте решим это:

  1. Для первых 5 чисел (подмассив из индекса 0–4) среднее значение равно (1 + 3 + 2 + 6–1) / 5 => 2,2
  2. Среднее значение следующих 5 чисел (подмассив из индекса 1–5): (3 + 2 + 6–1 + 4) / 5 => 2,8
  3. Для следующих 5 подмассивов чисел (подмассив из индекса 2–6) среднее: (2 + 6–1 + 4 + 1) / 5 => 2,4

Вот окончательный вывод, содержащий среднее значение всех подмассивов размера 5:

Выход: [2.2, 2.8, 2.4, 3.6, 2.8]

Алгоритм грубой силы рассчитает сумму каждого 5-элементного подмассива данного массива и разделит сумму на «5», чтобы найти среднее значение.

Есть ли лучшее решение? Нашли ли вы какую-либо неэффективность в приведенном выше подходе? На самом деле есть лучшее решение: эффективным способом решения этой проблемы было бы визуализировать каждый подмассив как скользящее окно из «5» элементов. Это означает, что мы сдвинем окно на один элемент при переходе к следующему подмассиву. Чтобы повторно использовать сумму из предыдущего подмассива, мы вычтем элемент, выходящий за пределы окна, и добавим элемент, который сейчас включается в скользящее окно.

Пример 02:

Постановка задачи

Учитывая массив положительных чисел и положительное число «k», найдите максимальную сумму любого непрерывного подмассива размера «k».

Массив: [2, 1, 5, 1, 3, 2], k = 3

Для этого каждый подмассив следует рассматривать как скользящее окно размера «k». Чтобы вычислить сумму следующего подмассива, нам нужно сдвинуть окно вперед на один элемент. Итак, чтобы сдвинуть окно вперед и вычислить сумму новой позиции скользящего окна, необходимы две вещи:

  1. Вычесть элемент, выходящий из скользящего окна, т. е. вычесть первый элемент окна.
  2. Добавьте новый элемент, включаемый в скользящее окно, т. е. элемент, следующий сразу за концом окна.

Пример 03:

Постановка задачи

Учитывая массив положительных чисел и положительное число «S», найдите длину наименьшего непрерывного подмассива, сумма которого больше или равна «S». Возвращает 0, если такой подмассив не найден.

Массив: [2, 1, 5, 2, 3, 2], S = 7

Вывод: 2
Объяснение: Наименьший подмассив с суммой больше или равной 7 — это [5, 2].

Мы можем использовать аналогичную стратегию, как обсуждалось в подмассиве максимальной суммы размера k. Однако есть одно отличие: в этой задаче размер скользящего окна не фиксирован. Вот как мы решим эту проблему.

Удивительная особенность задач со скользящим окном заключается в том, что в большинстве случаев их можно решить за O(N) времени и O(1) пространственной сложности.