Скользящее окно (переменное)

O(n)

Растим окно справа; как только условие нарушилось, сужаем слева. Оба конца движутся только вперёд, поэтому весь проход O(n).

Сигналы

самый длинный/короткий непрерывный подмассив или подстрокаудовлетворяющий условию (сумма <= K, не более, без нарушения лимита)не более K различных, без повторов, содержит все из Xнепрерывный отрезок, не подпоследовательность

Шаблон

function longestUnder(arr, limit) {
    let left = 0;
    let sum = 0;
    let best = 0;
    for (let right = 0; right < arr.length; right++) {
        sum += arr[right];
        while (sum > limit) {
            sum -= arr[left];
            left++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Похоже, но не то

Два указателя (с концов): Указатели с концов стартуют врозь и сходятся к одной паре на отсортированном массиве. У окна оба конца идут в одну сторону и хранят живой отрезок; отсортированный вход ему не нужен.
Префиксные суммы: Префиксные суммы отвечают на много произвольных запросов суммы на отрезке после O(n) подготовки. Окно делает один проход ради единственного лучшего отрезка; если значения бывают отрицательными, шаг сужения ломается и в дело идут префиксные суммы.

n до 1e5..1e6, один лучший непрерывный отрезок при монотонном условии -> O(n): каждый конец продвигается не более n раз.

Изучить этот паттерн