Два указателя на Python: как решать + 13 задач с проверкой

«Два указателя» (или *two pointers*) — это способ решать задачи про массивы и строки, где нужно что-то найти/посчитать для отрезков или пар элементов, не перебирая всё квадратично. Он часто встречается в задачах про «максимальный подряд идущий участок по ограничению» (как про бюджет на обеды), про подсчёт пар с условием разности/суммы, про слияние двух отсортированных списков (логов двух роботов), про поиск «слишком близких» значений.

Как распознать задачу под два указателя:

• В условии есть «подряд», «отрезок», «подстрока», «окно» и просят максимум/минимум длины или число подходящих отрезков.
• Ограничение монотонное: если расширять отрезок вправо, значение (сумма, число плохих элементов, количество разных) меняется предсказуемо, и можно «исправить» ситуацию сдвигом левой границы.
• Часто отдельно сказано, что числа неотрицательные (тогда сумма окна только растёт при движении правого указателя).
• Либо даны два отсортированных массива/указатели по времени — и нужно пройти их «встык».

Суть приёма: держим два индекса l и r, которые задают текущий отрезок, и поддерживаем его характеристику (например, сумму). Двигаем r вперёд, пока можно, а когда условие нарушено — двигаем l, пока снова не станет хорошо. Так каждый индекс проходит массив максимум один раз, и вместо O(n^2) получается O(n).

С чего начать учиться:

• Отработать «скользящее окно» на неотрицательных числах: максимум длины при сумме не больше k.
• Научиться поддерживать инвариант: что именно всегда верно про текущий отрезок.
• Потренироваться на двух отсортированных массивах: слияние, подсчёт пар, поиск ближайших.
• Всегда проверять типы: суммы и ответы часто требуют 64-битные значения.

Ниже — задачи с автопроверкой и разбором подхода: начни с простых окон, затем переходи к парам и слиянию.