Эти два паттерна часто встречаются в алгоритмах, особенно в задачах на массивы и строки. Они помогают снизить сложность решения с O(n²) до O(n) и часто используются на собеседованиях и в продакшене.
1. Два указателя 👉👈
Идея: держим два индекса и двигаем их по определённому правилу.
Где применяется:
- поиск пары с нужной суммой в отсортированном массиве
- удаление дубликатов
- разворот массива
- сравнение символов с двух концов строки
- разбиение массива по условию
Типичный сценарий:
- один указатель стоит в начале, второй — в конце
- если текущее состояние не подходит, двигаем один из них
- за счёт упорядоченного движения не проверяем лишние комбинации
Пример: найти пару чисел с суммой target в отсортированном массиве.
Если сумма меньше target — двигаем левый указатель вправо.
Если больше — правый влево.
Так мы не перебираем все пары.
2. Скользящее окно 🪟
Это частный случай двух указателей, когда мы работаем с непрерывным подмассивом или подстрокой.
Где применяется:
- максимальная сумма подмассива длины
k - самая длинная подстрока без повторяющихся символов
- минимальный подмассив с суммой не меньше
S - задачи на частоты символов
- поиск анаграмм в строке
Как работает:
- правый указатель расширяет окно
- левый — сужает, когда условие нарушено
- внутри окна поддерживаем нужное состояние: сумму, количество уникальных символов, частоты
Фиксированное окно
Размер известен заранее, например k.
Используется, когда нужен анализ всех подмассивов одинаковой длины.
Пример:
- найти максимальную сумму среди всех подмассивов длины
k
Вместо пересчёта суммы каждый раз:
- добавляем новый элемент справа
- убираем старый слева
Динамическое окно 🔍
Размер окна меняется в зависимости от условия.
Пример:
- найти самую длинную подстроку без повторов
Расширяем окно, пока символы уникальны.
Если встретили повтор — двигаем левую границу, пока условие снова не выполнится.
Как понять, что нужен этот паттерн 💡
- массив или строка
- нужно найти подмассив / подстроку
- требуется “самый длинный”, “минимальный”, “количество”
- есть условие на сумму, уникальность, частоты
- важна линейная сложность
Частые ошибки 🚨
- путаница между фиксированным и динамическим окном
- неверное обновление состояния при сдвиге левой границы
- попытка применить окно там, где нужен префиксный массив или хеш-таблица
- игнорирование случаев с отрицательными числами — не все техники окна там работают корректно
Итог
- Два указателя — общий подход для оптимизации перебора
- Скользящее окно — лучший выбор для непрерывных диапазонов
- Оба паттерна критически важны для задач на строки, массивы и performance-оптимизацию
📚 Сохраните пост как шпаргалку и загляните в подборку каналов про IT — там ещё больше полезных материалов по алгоритмам, разработке и карьере.