Два указателя и скользящее окно

Задача: в упорядоченном по неубыванию списке найти два числа с суммой $x$.

Перебор пар — квадрат. Но список упорядочен, и это позволяет действовать иначе. Поставим один указатель в начало, другой в конец:

left = 0
right = len(a) - 1

while left < right:
    total = a[left] + a[right]
    if total == x:
        print("YES")
        break
    if total < x:
        left += 1        # нужна сумма побольше
    else:
        right -= 1       # нужна сумма поменьше

Почему это верно? Если сумма мала, то самый левый элемент не подойдёт ни к кому: он уже сложен с наибольшим из оставшихся, и больше не станет. Значит его можно отбросить, ничего не потеряв. Симметрично для правого.

Каждый шаг отбрасывает элемент, поэтому шагов не больше $n$. Вместо квадрата — один проход.

Важно, что список упорядочен. Именно порядок позволяет утверждать «больше не станет». Если данные не упорядочены, приём начинают с сортировки — она стоит $n \log n$ и всё равно дешевле квадрата.

Второй вид приёма: оба указателя идут в одну сторону и ограничивают отрезок — окно.

Задача: найти самый длинный кусок с суммой не больше $s$, числа неотрицательные.

left = 0
total = 0
best = 0

for right in range(n):
    total += a[right]              # окно выросло вправо
    while total > s:
        total -= a[left]           # стало слишком много — жмём слева
        left += 1
    if right - left + 1 > best:
        best = right - left + 1

Обратите внимание: внутри цикла есть while, но квадрата не получается. Левая граница только растёт и никогда не возвращается, поэтому за всю работу она сделает не больше $n$ шагов. Всего — $2n$ действий.

Считаем сумму поправками, а не заново. Вошёл элемент — прибавили, вышел — вычли. Это та же мысль, что была в задачах про окно фиксированной длины.

И полезный приём для подсчёта: когда правая граница на месте, все подходящие куски с этим правым концом — это отрезки, начинающиеся от left и правее. Их ровно right - left + 1, и складывая эти количества, получаем ответ на вопрос «сколько всего кусков подходит».

Внутри цикла for right стоит цикл while, который двигает левую границу.

Сколько всего действий сделает такое решение?

Окно работает не всегда, и это главное, что нужно унести с занятия.

Приём держится на монотонности: расширение окна вправо должно ухудшать свойство, а сжатие слева — улучшать. Тогда понятно, что делать, и понятно, что ничего не потеряно.

Для суммы это верно, только пока числа неотрицательны. Добавили элемент — сумма не уменьшилась. Убрали — не увеличилась.

Контрпример

Пусть в списке есть отрицательные числа: 5 -4 3, и ищем самый длинный кусок с суммой не больше 4.

Окно начинает с 5 — сумма 5, это больше четырёх, левая граница подтягивается, и элемент теряется. Но кусок 5 -4 3 имеет сумму 4 и подходит целиком! Приём отбросил ответ, потому что рассуждение «дальше будет только хуже» перестало быть верным.

Поэтому в задачах на окно с суммой всегда написано, что числа неотрицательны. Это не украшение условия, а обязательное требование.

Для сумм с отрицательными числами есть другой инструмент — префиксные суммы со словарём из прошлого занятия.

Окно не обязано хранить только сумму. Часто внутри держат словарь частот — тогда можно следить за составом.

counts = {}
left = 0

for right in range(n):
    counts[a[right]] = counts.get(a[right], 0) + 1
    while len(counts) > k:                 # слишком много различных
        value = a[left]
        counts[value] -= 1
        if counts[value] == 0:
            del counts[value]              # значение ушло совсем
        left += 1

Строка с del — не мелочь. Без неё в словаре останутся ключи с нулевым счётчиком, и len(counts) будет считать значения, которых в окне уже нет.

Такое окно решает целое семейство задач: «не больше $k$ различных», «все значения сразу», «сколько различных в каждом окне длины $k$».

А ещё им считают противоположное. Вопрос «сколько кусков с суммой не меньше $s$» окном напрямую не решается — зато решается вопрос «сколько кусков с суммой меньше $s$», а общее количество кусков известно: их $n(n+1)/2$. Вычитание даёт ответ.

Правая граница окна стоит на пятом элементе, левая — на втором. Номера с единицы.

Сколько кусков заканчиваются пятым элементом и целиком помещаются в окно? Введите целое число.

Окно применили там, где нет монотонности. Отрицательные числа в задаче на сумму — сразу повод усомниться. Признак: ответ верен на большинстве тестов и неверен там, где выгодно взять кусок «через минус».

Левая граница обогнала правую. В задачах со строгим неравенством while может сдвинуть левую границу за правую, и длина окна станет отрицательной. Добавляйте условие left <= right.

Забытое удаление ключа. Счётчик обнулился, а ключ остался — и количество различных считается неверно. Признак: ответ завышен и растёт с длиной списка.

Как проверять себя

• все элементы одинаковые — окно должно растянуться на весь список;
• ответа не существует — что выводится по условию;
• список из одного элемента;
• порог, равный нулю — там строгие и нестрогие неравенства расходятся.

Лестница прежняя: пять разминочных, семь основных, три со звёздочкой. Зачёт при десяти решённых.

Задачи двух видов: указатели навстречу в упорядоченном списке и окно, идущее в одну сторону. В части задач список уже упорядочен по условию, в части его надо отсортировать самому.

Обращайте внимание на слово «неотрицательные» в условиях — там, где оно есть, окно применимо, и это сказано не случайно.

Задача: «дан список из $n$ целых чисел — любых, включая отрицательные — и число $s$; найдите наибольшую длину куска из подряд идущих элементов с суммой не больше $s$».

Ученик написал:

n, s = map(int, input().split())
a = list(map(int, input().split()))

left = 0
total = 0
best = 0

for right in range(n):
    total += a[right]
    while total > s:
        total -= a[left]
        left += 1
    if right - left + 1 > best:
        best = right - left + 1

print(best)

На тестах без отрицательных чисел решение верно. Постройте вход, на котором оно ошибается, объясните, какое рассуждение перестало работать, и скажите, чем такую задачу решать.