Два указателя

Перебрать все отрезки массива — это $O(n^2)$. Приём двух указателей сводит перебор к линии, но работает не всегда, и понимать границу применимости важнее, чем помнить код.

Схема

int left = 0;
long long sum = 0;
for (int right = 0; right < n; right++) {
    sum += a[right];                    // добавили правый
    while (условие нарушено) {
        sum -= a[left];                 // убрали левый
        left++;
    }
    // здесь окно [left, right] — лучшее из тех, что кончаются в right
}

Правая граница сдвигается ровно $n$ раз. Левая только растёт и тоже проходит не больше $n$ шагов за всё время. Значит, тело внутреннего цикла выполнится суммарно не больше $n$ раз, сколько бы ни было вложенности.

Это амортизация: оценивать надо не «сколько шагов на итерации», а «сколько шагов за всю работу».

Условие применимости

Приём опирается на монотонность: если окно не годится, то и любое его расширение влево не годится.

Для суммы это верно при неотрицательных числах: добавление элемента сумму не уменьшает. Именно поэтому в условиях таких задач всегда написано «числа положительные» — это не украшение, а то, на чём стоит решение.

С отрицательными числами свойство ломается. Возьмите 5 -5 1 и $S = 1$: весь массив даёт сумму 1 и годится, ответ 3. А два указателя выдадут 2 — левая граница уедет вправо на первом же шаге и назад уже не вернётся.

Здесь нужны префиксные суммы: ищем наименьший $l$, при котором $prefix_r - prefix_{l-1} \le S$, а это уже задача поиска в множестве префиксов.

Что можно нести в окне

Сумма — простейший случай. Годится всё, что дёшево пересчитывается при добавлении справа и удалении слева:

Что несём	Чем поддерживается	Пример задачи
сумма	числом	отрезок с суммой не больше $S$
число различных значений	счётчиками в массиве или словаре	отрезок с не более чем $k$ различными
сколько типов покрыто	счётчиками по типам	окно, содержащее все требуемые элементы
максимум и минимум	двумя очередями	отрезок с разбросом не больше $k$

Последняя строка — отдельная тема, ей посвящена статья про очередь с минимумом.

Два указателя в двух массивах

Второй вид задачи: указатели идут по разным массивам.

Например, оба массива отсортированы, и для каждого элемента второго надо узнать, сколько в первом элементов строго меньше него.

int i = 0;
for (int j = 0; j < m; j++) {
    while (i < n && a[i] < b[j]) i++;
    answer[j] = i;              // столько элементов a меньше b[j]
}

Работает потому, что $b$ отсортирован: всё, что было меньше предыдущего элемента, меньше и следующего. Указатель i только растёт — снова линия.

Тот же приём — основа слияния двух отсортированных массивов, а через него и сортировки слиянием.

Порядок действий имеет значение

Сначала добавляем правый, потом чиним левым. Обратный порядок допускает состояние с пустым окном и обращение к несуществующему элементу.

И ещё: условие внутреннего цикла обязано проверять границы раньше, чем содержимое. while (left <= right && sum > S) — правильно; переставьте местами, и на пустом окне программа заглянет в чужую память.