Два указателя и скользящее окно: приёмы для задач на массивы

Суть за одну минуту

Перебор «каждый с каждым» — это два вложенных цикла и O(n²). Оба приёма убирают внутренний цикл:

• Два указателя — два индекса, которые движутся по массиву навстречу друг другу или в одну сторону с разной скоростью.
• Скользящее окно — непрерывный отрезок [left, right], который расширяется справа и сужается слева, а нужная величина (сумма, счётчик символов) обновляется за O(1).

Ключевая мысль: каждый указатель только идёт вперёд и проходит не больше n шагов, поэтому общая работа — O(n).

Как распознать паттерн

Если отрезок не обязан быть непрерывным или в массиве есть отрицательные числа, а условие про сумму, окно обычно не работает — смотрите в сторону префиксных сумм или хеш-таблиц.

Задача 1. Пара с заданной суммой в отсортированном массиве

Перебор проверяет все пары — O(n²). С двумя указателями: если сумма мала, двигаем левый вправо, если велика — правый влево.

def pair_with_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return left, right
        if s < target:
            left += 1
        else:
            right -= 1
    return None

Время O(n), память O(1). Работает только потому, что массив отсортирован: сдвиг указателя гарантированно отбрасывает пары, которые не подойдут.

Задача 2. Удалить дубликаты из отсортированного массива на месте

Медленный указатель write показывает, куда писать следующий уникальный элемент, быстрый read идёт по массиву.

def dedupe_sorted(nums):
    if not nums:
        return 0
    write = 1
    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:
            nums[write] = nums[read]
            write += 1
    return write  # длина уникальной части

Время O(n), память O(1) — без создания нового списка.

Задача 3. Максимальная сумма подмассива длины k

Перебор считает сумму каждого окна заново — O(n·k). Окно фиксированного размера: при сдвиге добавляем вошедший элемент и вычитаем вышедший.

def max_sum_k(nums, k):
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]
        best = max(best, window)
    return best

Время O(n). Предполагается, что 1 <= k <= len(nums).

Задача 4. Самая длинная подстрока без повторяющихся символов

Окно переменного размера: расширяем справа, а при повторе сдвигаем левую границу за предыдущее вхождение символа.

def longest_unique(s):
    last_seen = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best

Перебор всех подстрок с проверкой уникальности — O(n²) и хуже. Здесь каждый индекс посещается один раз: O(n) времени и память на размер алфавита.

Задача 5. Кратчайший подмассив с суммой не меньше target

Числа положительные. Расширяем окно, пока сумма меньше target, затем сжимаем слева, пока условие выполняется, и запоминаем минимальную длину.

def min_len_subarray(nums, target):
    left = total = 0
    best = float("inf")
    for right, x in enumerate(nums):
        total += x
        while total >= target:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best

Вложенный while не делает решение квадратичным: left за весь проход сдвигается не больше n раз, поэтому итог — O(n).

Шаблон окна переменного размера

1. Двигайте right по массиву и добавляйте элемент в состояние окна.
2. Пока окно нарушает условие (или, наоборот, удовлетворяет — для поиска минимума), сдвигайте left и убирайте элемент из состояния.
3. После каждого шага обновляйте ответ.

Частые ошибки

• Применять окно к массиву с отрицательными числами в задачах на сумму — сжатие слева уже не гарантирует уменьшение суммы.
• Забывать про пустой массив и k > len(nums).
• Ошибки на единицу в длине окна: она равна right - left + 1.
• В задаче 4 не проверять, что прошлое вхождение символа внутри текущего окна.