Основная идея метода скользящего окна или sliding window заключается в поддержании диапазона или "окна" элементов, которое "скользит" по массиву или строке.
Метод скользящего окна позволяет улучшить вычислительную сложность до линейной, а по памяти — до константной.
Как работает
Представим, что у нас есть массив и нужно найти в нем подмассив, который удовлетворяет определенным условиям. Вместо того чтобы рассматривать каждый возможный подмассив отдельно, мы создаем окно фиксированной или переменной длины, которое перемещается по массиву. Над этим окном мы выполняем необходимые вычисления.
Когда использовать метод скользящего окна?
передаётся упорядоченная и итерируемая структура данных, вроде массива или строки;
нужно найти подпоследовательность в массиве/строке, самое длинное/короткое, среднее/большое/маленькое и т. д.
Примеры задач в которых используем sliding window
Нахождение максимальной суммы подмассива фиксированной длины: Используем скользящее окно длиной k, которое перемещается по массиву, поддерживая сумму текущих k элементов.
Нахождение самой длинной подстроки без повторяющихся символов: Окно расширяется, когда добавляется новый символ, который ранее не встречался, и сжимается, когда обнаруживается повторение.
Нахождение минимального размера подмассива с суммой равной заданному числу: Здесь окно также имеет переменную длину. Окно расширяется, когда добавляется новый элемент, увеличивая сумму, и сжимается, когда сумма превышает заданное число, чтобы найти минимально возможную длину.
Подсчет количества различных символов в каждом подмассиве: Скользящее окно применяется для перебора всех подмассивов заданной длины, подсчитывая уникальные символы в каждом из них.
Задача с реального собеседования с решением на Go
Дан массив целых положительных чисел, нужно найти подотрезок с заданной суммой target, либо сказать, что это невозможно.
Пример: Массив [9, 6, 5, 1, 4, 2] и target 10. Цифры 5, 1, и 4 дают в сумме 10 и идут последовательно, возвращаем их индексы в виде подотрезка [2, 4].
Решение
- Инициализируем два указателя, начальный (start) и конечный (end), оба устанавливаются в начало массива.
- Переменную windowSum хранит текущую суммы скользящего окна.
- Двигаем конечный указатель (end) по массиву, увеличивая windowSum.
- Как только windowSum равна или превышает target, начинаем сдвигать начальный указатель (start), уменьшая windowSum, пока она не станет меньше target.
- Если в какой-то момент windowSum равна target, возвращаем подотрезок (индексы start и end).
- Если такого подотрезка не нашлось, возвращаем [-1, -1].
Алгоритм скользящего окна становится неприменимым в ситуации, когда в массиве будут отрицательные числа. В таком случае надо использовать другой подход, например, префиксные суммы в сочетании с хэш-таблицей. Рассмотрим его в следующей статье.