Окно переменного размера с двумя указателями
Расширяйте и сужайте окно до выполнения условия
«Окно переменного размера с двумя указателями» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Когда окно меняет размер
В некоторых задачах длина окна не фиксирована. Вместо этого окно увеличивается и уменьшается, чтобы условие оставалось истинным, например чтобы сумма не превышала заданный предел.
Два указателя, одно окно
Храните два индекса — левый и правый, обозначающие границы окна. Правый указатель расширяет окно, а левый следует за ним и при необходимости уменьшает окно.
left = 0
window = 0Расширяйте вправо
Пройдите вправо по каждому элементу и включите его в окно. Обновляйте текущее состояние, например добавляйте новое значение к сумме.
for right in range(n):
window += a[right]Уменьшайте при необходимости
Пока окно нарушает правило, перемещайте левую границу вправо и удаляйте соответствующий элемент. Это восстановит условие без возврата назад.
while window > limit:
window -= a[left]
left += 1Считайте корректное окно
После завершения внутреннего цикла окно от левой границы до правой является корректным. Его длина равна правой границе минус левой плюс один — значение готово к использованию.
length = right - left + 1Записывайте лучший результат
Обновляйте ответ с помощью этого корректного окна — часто нужно найти самое длинное из просмотренных. Делайте это на каждой итерации, чтобы ничего не пропустить.
best = max(best, right - left + 1)Почему сложность линейна
Каждый указатель движется только вперёд и никогда не возвращается назад. Вместе левый и правый указатели перемещаются не более чем на n шагов, поэтому весь проход имеет сложность O(n).
Монотонное требование
Этот подход работает, когда расширение окна лишь делает условие более трудным для выполнения. Именно такое монотонное поведение позволяет левому указателю никогда не возвращаться назад.
Самое длинное и самое короткое
Чтобы найти самое короткое корректное окно, уменьшайте его, пока правило всё ещё выполняется, и сохраняйте результат перед нарушением правила. Механика указателей остаётся той же.
while window >= target:
best = min(best, right - left + 1)
window -= a[left]
left += 1Остерегайтесь пустых окон
Если уменьшение может сделать окно пустым, предусмотрите случай, когда левая граница проходит правую. Также убедитесь, что ответ действительно найден, прежде чем возвращать его.
Распознавайте этот шаблон
Используйте окно переменной длины, когда в задаче требуется найти самый длинный или самый короткий непрерывный фрагмент, элементы которого удовлетворяют условию.
Быстрая проверка
Вы применяете окно переменной длины с двумя указателями к массиву размера n.
Итоги
Расширяйте правую границу, включая элементы, уменьшайте окно слева, пока правило нарушается, и сохраняйте каждое корректное окно. Указатели, движущиеся только вперёд, обеспечивают сложность O(n). ✅
Часто задаваемые вопросы
Урок «Окно переменного размера с двумя указателями» бесплатный?
Да — полный текст урока «Окно переменного размера с двумя указателями» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Окно переменного размера с двумя указателями»?
Расширяйте и сужайте окно до выполнения условия Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.
Сколько времени занимает урок «Окно переменного размера с двумя указателями»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Суммы окон фиксированного размера
- Окно переменного размера с двумя указателями
- Самая длинная подстрока без повторов
- Подсчёт окон, удовлетворяющих правилу