Алгоритмы на строках и массивах: префиксные суммы, хеш-таблицы и двухуказательные техники

Многие задачи на собеседованиях и в реальных проектах сводятся к одной и той же абстракции: «найти фрагмент» — подстроку или подмассив, удовлетворяющий условию. На первый взгляд кажется, что это разные миры (строки и массивы), но на практике решения часто строятся из одних и тех же паттернов.

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

Речь пойдёт о паттернах:

• префиксные суммы и их обобщения;
• скользящее окно;
• хеш-таблицы для подсчёта и поиска по “значениям префиксов”;
• двухуказательные техники (две границы/пойнтеры) и их инварианты;
• объединение идей для строк и массивов.

Базовая модель: что мы ищем и какой “инвариант” нужен

Почти любую задачу на подмассив или подстроку можно переписать в виде одного из условий:

1. Ровно / не больше / не меньше суммы на отрезке:
   • sum(l..r) = K, <= K, >= K
2. Поиск фрагмента по равенству:
   • подстрока как последовательность символов,
   • подмассив как последовательность чисел,
   • подстрока/подмассив с некоторыми ограничениями на частоты.
3. Подсчёт количества фрагментов, удовлетворяющих условию.

Инвариант — это утверждение вида: «на каждой итерации, при движении границ, мы знаем, что именно контролируем». Например:

• Для префиксных сумм инвариант обычно такой:
  sum(l..r) = pref[r] - pref[l] и мы ищем пары префиксов с нужной разницей.
• Для скользящего окна:
  «между l и r мы поддерживаем структуру данных (частоты/сумму), соответствующую ограничению».
• Для двух указателей (two pointers) по монотонным свойствам:
  «если условие нарушено при текущем l, то увеличение l монотонно улучшает ситуацию» (например, при неотрицательных элементах).

Самое важное: выбор техники определяется свойствами данных (например, неотрицательность), а не только формулировкой задачи. Два человека могут решить одну и ту же “словесную” задачу, но их решения будут разными из‑за скрытых условий.

Префиксные суммы: быстрый доступ к сумме на отрезке

Что дают префиксные суммы

Для массива a[0..n-1] префиксные суммы:

• pref[0] = 0
• pref[i+1] = pref[i] + a[i]

Тогда сумма на отрезке [l, r] (включительно) равна:

• sum(l..r) = pref[r+1] - pref[l]

Инвариант: разность двух префиксов — это сумма между соответствующими индексами.

Это базовый кирпич для задач вида:

• найти подмассив с суммой K,
• посчитать количество подмассивов с суммой K,
• найти минимум/максимум по сумме или с ограничением суммы (в сочетании с дополнительными структурами).

Подмассив с суммой K: от поиска к хеш-таблице

Если a[i] могут быть отрицательными, то двухуказательные техники “с монотонностью” чаще всего ломаются. Зато префиксы + хеш дают универсальное решение.

Пусть мы идём по r и хотим найти l, чтобы:

pref[r+1] - pref[l] = K
pref[l] = pref[r+1] - K

Идея: храним в хеш-таблице, сколько раз встречался каждый pref[l] до текущего индекса.

Пример кода (подсчёт количества подмассивов с суммой K):

from collections import defaultdict

def count_subarrays_sum_k(a, k):
    pref = 0
    freq = defaultdict(int)
    freq[0] = 1  # pref[l] когда l=0

    ans = 0
    for x in a:
        pref += x
        need = pref - k
        ans += freq[need]
        freq[pref] += 1
    return ans

Инвариант: на шаге обработки текущего r хеш-таблица содержит частоты всех pref[l] для l <= r.

Типичная ошибка №1: забыть про pref[0]

Если не положить freq[0] = 1, то вы не учтёте случаи, где нужный подмассив начинается с нулевого индекса.

Типичная ошибка №2: пытаться использовать two pointers при отрицательных

Если в массиве есть отрицательные, сумма может “скакать” при движении границ, а монотонность рушится. Хеш-таблица становится надёжным универсальным вариантом.

Префиксные суммы и строки: как переписать подстроку в терминах сумм

Когда префиксы подходят к подстрокам

Строковые задачи часто сводятся к числам через:

• префикс по ASCII/кодам (реже),
• префикс по частотам символов (для ограничений на состав),
• “преобразованиям” вида +1/-1 (например, баланс скобок),
• префиксам по массивам признаков (например, b[i] = 1 если s[i]=... иначе 0).

Например, баланс скобок для строки из ( и ):

• пусть b[i] = +1 для ( и -1 для );
• тогда баланс на префиксе — обычная сумма по b.

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

Скользящее окно: когда можно поддерживать ограничение при расширении правой границы

Базовая идея

Скользящее окно — это техника с двумя границами l и r, где мы:

1. расширяем r (добавляем новый элемент в окно);
2. пока условие нарушено — сдвигаем l (удаляем элементы из окна);
3. когда условие выполнено — фиксируем ответ.

Инвариант: на каждом этапе окно [l, r] удовлетворяет некоторому ограничению (после цикла “пока нарушено — сжимаем”).

Пример: минимальная длина подмассива с суммой >= K (неотрицательные элементы)

Эта задача классическая:

• найти минимальную длину len такого, что sum(l..r) >= K,
• элементы массива неотрицательны.

Почему именно неотрицательность? Потому что при расширении r сумма растёт или не уменьшается, а при сдвиге l сумма уменьшается/не растёт. Это обеспечивает монотонность и корректность “сжимания”.

Код:

import math

def min_len_subarray_sum_ge_k(a, k):
    n = len(a)
    l = 0
    s = 0
    ans = math.inf

    for r in range(n):
        s += a[r]
        while s >= k:
            ans = min(ans, r - l + 1)
            s -= a[l]
            l += 1

    return ans if ans != math.inf else 0

Инвариант: в цикле while s >= k мы перебираем все “левые” варианты, которые всё ещё дают сумму ≥ K, и уменьшаем длину.

Типичная ошибка №3: игнорировать отрицательные

Если в массиве есть отрицательные элементы, то при сдвиге l сумма может как уменьшиться, так и увеличиться — алгоритм перестаёт быть корректным.

Пример: подмассивы с максимумом/минимумом по условию через “окно по инварианту”

Скользящее окно часто используется и для задач с частотами, когда ограничение формулируется как:

• “в окне не более K различных элементов”,
• “в окне не более K нарушений/несоответствий”,
• “в окне не более K символов, отличных от заданного”.

Тут инвариант обычно выражается через счётчики частот в структуре данных.

Двухуказательные техники: не только окно, но и “монотонность”

Термин “two pointers” часто смешивают со скользящим окном. На практике различие в том, что:

• скользящее окно обычно фиксирует инвариант “окно удовлетворяет ограничению” и “сжимается/расширяется”;
• двухуказательные решения часто опираются на более общие свойства: монотонность функции или упорядоченность данных (например, после сортировки).

Two pointers на отсортированном массиве: пары/тройки

Например, найти пары с суммой K (когда массив отсортирован):

• i слева, j справа,
• если a[i] + a[j] < K — увеличиваем i,
• если > K — уменьшаем j,
• если равно — фиксируем ответ и сдвигаем обе границы (с учётом повторов).

Инвариант: при движении i и j мы отсекаем невозможные пары, сохраняя возможность найти нужную сумму.

Когда двухуказательные ломаются

• Если данные не упорядочены и нет монотонного критерия.
• Если условие требует точного учёта комбинаций при отсутствии структуры (тогда чаще нужна хеш-таблица или префиксы).

Хеш-таблицы: когда равенство префиксов превращается в подсчёт

Хеширование — это способ превратить “поиск по индексу” в “поиск по значению”. Самый частый сценарий — задачи про сумму на отрезке или “встречаемость” некоторого состояния.

Префиксы + хеш: количество подмассивов с суммой K

Мы уже рассмотрели шаблон для количества. Он часто встречается и в строковых задачах, если состояние подстроки выражается разностью префиксов.

Ещё один паттерн: “одинаковые префиксы” и нулевая сумма

Когда pref[r+1] - pref[l] = 0:

pref[r+1] = pref[l]

Тогда количество подмассивов с нулевой суммой можно посчитать как сумма по значениям префикса:

• если некоторое значение встречается c раз среди префиксов, то пар (l, r) будет c*(c-1)/2.

В коде можно сделать либо так, либо обойти массив один раз, аккумулируя хеш частоты.

Как выбрать технику: практическая таблица решений

Ниже — не “рецепт на все случаи”, а быстрый ориентир по инвариантам и по свойствам данных.

Задачи про сумму на отрезке

1) Есть отрицательные числа и нужно найти/посчитать суммы K

• Обычно: префиксы + хеш.
• Инвариант: pref[r] - pref[l] = K.

2) Все числа неотрицательные и нужно оптимизировать по длине/условиям вида “сумма >= K”

• Обычно: скользящее окно / two pointers.
• Инвариант: монотонность суммы при расширении/сжатии.

3) Нужно много запросов к разным K или сравнениям

• Часто: префиксные суммы + дополнительная структура (хеш для каждого K может быть дорогим; иногда применяют оффлайн-подходы, но это отдельная тема).

Задачи про “подстрока с ограничениями на частоты”

• Если ограничения вида “не более K различных символов” или “не более K ошибок/несоответствий”:
  • обычно скользящее окно с частотами и инвариантом на счётчики.
• Если требуется “подстрока как точная последовательность”:
  • часто нужны другие алгоритмы (Кнут–Моррис–Пратт, Рабин–Карп и т.д.), но это выходит за рамки текущей статьи — мы фокусируемся на префиксах/хеш/двухуказательных для ограничений и сумм.

Типовые ошибки и подводные камни

Ошибка 1: неверный инвариант (окно “почти удовлетворяет” условию)

Скользящее окно корректно, когда после внутреннего сжатия окно действительно удовлетворяет ограничению. Если вы фиксируете ответ “пока условие не нарушено”, но забываете, что нарушение уже случилось и окно нужно сжимать — ответ будет завышен.

Практический тест: выпишите состояние окна перед фиксированием ответа. Если условие ещё не доказано как выполненное — значит, алгоритм может быть неверным.

Ошибка 2: смешивание индексов (включительно/исключительно) в префиксах

В префиксах часто удобно работать с полузакрытыми интервалами:

• сумма на [l, r) равна pref[r] - pref[l].

Если начать “на глаз” смешивать включительно/исключительно, легко получить на один индекс ошибку, особенно когда формула стоит в коде “как есть”.

Ошибка 3: переполнение и типы данных

В языках вроде C++/Java нужно внимательно к типам: сумма префиксов может быть больше диапазона int. На Python это не проблема, но алгоритмические инварианты сохраняются.

Ошибка 4: хеш-таблица без продуманной структуры

Для подсчёта количества подмассивов с суммой K хеш должна хранить частоты, а не просто “видели/нет”. Если хранить boolean, вы потеряете количество вариантов и сломаете подсчёт.

Ошибка 5: попытка “угадать” монотонность

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

Практические “сквозные” шаблоны: как думать на задачах

Шаблон A: “условие на сумму” → префиксные суммы

1. Переопределите сумму на отрезке через префиксы.
2. Выпишите требуемое равенство/неравенство в терминах pref.

Пример:

• sum(l..r) = K → pref[r+1] - pref[l] = K → pref[l] = pref[r+1] - K.

Дальше варианты:

• если нужны точные индексы/количество — используйте хеш;
• если есть неотрицательность и нужна оптимизация длины — пробуйте окно.

Шаблон B: “ограничение на окно” → инвариант окна

1. Опишите, что именно должно быть верным “для окна”.
2. Настройте обновление при движении r.
3. Добавьте цикл “пока нарушено — двигаем l”.
4. Фиксируйте ответ только когда инвариант восстановлен.

Шаблон C: “монотонная функция/отсортированность” → двухуказательные

1. Ищем пару/тройку на отсортированном массиве или условие, которое улучшается при движении указателей.
2. Выводим, что происходит при сравнении текущего значения с целевым.
3. Доказываем, что при движении указателя вы не пропускаете решения.

Где именно эти техники “пересекаются” на строках и массивах

Хотя формально строки и массивы разные, многие задачи одинаково выглядят после преобразования:

• Подстрока с условием по балансу скобок → массив знаков +1/-1 → префиксы + хеш.
• Подстрока/подмассив с ограничением по количеству определённых объектов → скользящее окно + частотные счётчики.
• Подмассивы с суммой и подстроки с суммой “признаков” (например, 1 для символа x, 0 иначе) → та же схема префикс/хеш.

Если вы на реальной задаче сможете явно “перевести” строку в последовательность чисел (частоты, признаки, баланс), то почти наверняка появится одна из обсуждённых техник.

Вывод: как системно прокачать навык выбора алгоритма

Ключ к продуктивным решениям — не запоминать техники “по названию”, а научиться быстро находить правильный инвариант:

• Префиксные суммы дают выражение суммы на отрезке как разности состояний.
• Хеш-таблица нужна, когда требуется быстро найти пары состояний