Алгоритмы trainee
Что такое скользящее окно?
Ответ
Поддерживаем «окно» — диапазон [left, right] в массиве. Двигаем right (расширяем), при нарушении условия — двигаем left (сужаем). Используется для подстрок без повторов, максимума в окне фиксированного размера. Сложность O(n).
Разбор: Скользящее окно поддерживает динамический диапазон [left, right]: right расширяет окно, а при нарушении условия left сужает его, не сбрасываясь в ноль, что даёт суммарно O(n). Ловушки: это не разбиение на независимые блоки и не «разделяй и властвуй», а сброс left = right ломает корректность для задач вроде подстроки без повторов, где left должен двигаться постепенно.
Хочешь так же по своей компании — с вопросами по грейдам и задачами? Закажи гайд или забери свежее в Telegram.