Ассоциативные массивы в задачах LeetCode

Введение: hash map, операции и сложность на LeetCode

Ассоциативный массив (он же hash map, словарь, map) — одна из самых полезных структур данных на LeetCode. Он позволяет быстро отвечать на вопросы вида: «сколько раз встречается значение?», «видели ли мы это раньше?», «где последний раз встречался элемент?».

В этом курсе мы будем разбирать типовые паттерны задач, где hash map даёт оптимальную асимптотику. В первой статье зафиксируем базу: что такое hash map, какие операции считаются стандартными, и почему в решениях на LeetCode почти всегда пишут про .

Что такое hash map

Hash map хранит пары ключ → значение.

Ключ — то, по чему мы ищем (например, число, строка, кортеж).

Значение — то, что хотим сохранить (например, счётчик, индекс, список индексов).

Основная идея: с помощью хеш-функции ключ преобразуется в число (хеш), которое помогает быстро выбрать место хранения.

!Диаграмма показывает путь от ключа к бакету и что происходит при коллизиях

Термины, которые встречаются в задачах

Hash function (хеш-функция): отображает ключ в число.

Bucket (бакет): «корзина»/ячейка внутри внутреннего массива.

Collision (коллизия): разные ключи дали один и тот же бакет.

Load factor (коэффициент заполнения): насколько плотно заполнена таблица; при росте обычно происходит rehash (перестройка), чтобы сохранить быструю работу.

Важно: реализация зависит от языка, но общая модель на LeetCode одинаковая — операции ожидаются в среднем быстрыми.

Базовые операции и их смысл в задачах LeetCode

Ниже — операции, которые вы почти всегда используете в решениях.

Вставка/обновление: map[key] = value

Поиск: проверить наличие ключа и/или получить значение

Удаление: удалить ключ (реже нужно на LeetCode, но встречается)

Итерация: пройти по ключам/значениям/парам

Частые микропаттерны

Счётчик частот: ключ = элемент, значение = количество.

Запоминание последней позиции: ключ = элемент, значение = индекс.

Группировка: ключ = признак группы, значение = список элементов.

Мемоизация: ключ = состояние (например, пара индексов), значение = ответ.

Сложность: почему пишут и когда это неправда

Средняя (амортизированная) сложность

В большинстве реализаций hash map:

поиск, вставка, обновление — в среднем

Почему «в среднем»:

Хеш-функция распределяет ключи по бакетам достаточно равномерно.

При росте таблицы происходит rehash: внутренний массив увеличивают, и элементы перераскладывают.

Поэтому на LeetCode вы часто увидите формулировку: Time: , Space: , где по времени берётся от одного прохода по массиву, а операции со словарём считаются .

Худший случай

Худший случай для hash map — когда много ключей попадает в один бакет (коллизии), и тогда операции могут деградировать до .

На практике в задачах LeetCode обычно:

либо входы не конструируются специально для атаки на хеш,

либо реализация в языке имеет защиты/хорошие хеши,

либо ожидается именно стандартная оценка «average ».

Это не значит, что о худшем случае можно забыть: он важен для понимания, почему hash map иногда ведёт себя медленнее на больших тестах или при неудачных ключах.

Что именно считается «ключом» и какие ключи подходят

Ключ должен быть:

хешируемым (можно вычислить хеш),

сравнимым на равенство (чтобы различать ключи при коллизиях).

Примеры:

числа, строки — почти всегда подходят

кортежи/пары фиксированной длины (например, (x, y)) — часто подходят

списки/массивы как ключ — часто не подходят (в Python список не хешируется)

Практический вывод для LeetCode: если вам нужно сделать ключом «набор параметров», чаще всего используют кортеж/строку/целое число, собранное из нескольких частей.

Hash map на LeetCode: типовые ситуации применения

Ниже — «сигналы» в формулировке задачи, что, вероятно, нужен hash map.

Нужно найти пару/тройку с условием (часто вместе с идеей дополнения до суммы).

Нужно проверить, встречался ли элемент раньше.

Нужно посчитать частоты и сравнить (анаграммы, уникальность, топ-K по частоте).

Нужно хранить соответствие «объект → индекс/позиция».

Нужно быстро отвечать на запросы «есть ли такой элемент?» при множественных проверках.

Нюансы по языкам (что чаще всего используют на LeetCode)

Python

Основная структура: dict.

Часто помогает collections.Counter и defaultdict.

Документация: Python dict, collections.Counter

Пример:

Java

Основная структура: HashMap<K, V>.

Документация: Java HashMap

Пример:

C++

Часто используют unordered_map.

Документация: C++ unordered_map

Пример:

JavaScript

Для ключей любого типа лучше подходит Map (а не обычный объект).

Документация: MDN Map

Пример:

Практический чек-лист перед тем как писать решение

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

Определите, что будет значением (счётчик, индекс, список, булево).

Проверьте, какие операции вам нужны: только чтение/запись или ещё удаление/сдвижение окна.

Оцените память: если ключей может быть до , то space часто будет .

Что дальше в курсе

Дальше мы будем разбирать конкретные паттерны LeetCode, где hash map — ключевой инструмент: подсчёт частот, поиск пар (Two Sum и аналоги), группировки (анаграммы), префиксные суммы с хеш-таблицей и техники для скользящего окна.

Частотные таблицы: counting, анаграммы и уникальность

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

В прошлой статье мы зафиксировали основу: ассоциативный массив хранит пары ключ → значение, а операции чтения/записи обычно считаются в среднем . Теперь применим это к самому практичному случаю: ключ = элемент, значение = счётчик.

Что такое частотная таблица и когда она нужна

Частотная таблица — это hash map, где:

ключ: элемент (число, символ, строка)

значение: сколько раз элемент встретился

Этот приём нужен, когда в задаче встречаются формулировки:

count / frequency / occurrences

unique / first unique / distinct

anagram / permutation

most frequent / top K / majority

Главный выигрыш: вместо вложенных циклов с поиском повторов вы делаете один проход и получаете компактное «резюме» данных.

Базовый шаблон counting

Идея: пройти по массиву (или строке) и увеличивать счётчик.

Python

Java

C++

JavaScript

Типовые задачи и решения-паттерны

Ниже — наиболее «экзаменационные» случаи, которые регулярно повторяются на LeetCode.

| Сигнал в задаче | Что хранить в map | Что делать после прохода | |---|---|---| | «посчитать частоты» | element → count | ответ из частот (максимум, сумма, фильтр) | | «первый уникальный» | element → count | второй проход: найти первый с count == 1 | | «анаграммы» | char → count или «подпись» | сравнить таблицы или подписи | | «удалить минимум, чтобы…» | element → count | анализировать частоты, выбирать кандидатов |

Уникальность и «первый уникальный»

Частая ловушка

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

Типичный подход:

Первый проход: построить freq.

Второй проход по исходному порядку: найти первый элемент с freq[element] == 1.

Пример задачи: First Unique Character in a String

Почему два прохода всё равно быстро

Вы делаете линейную работу дважды, но это всё равно линейно по времени, потому что это два последовательных прохода, а не вложенные циклы.

Анаграммы: сравнение частот

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

Пример задачи: Valid Anagram

Подход через частотные таблицы

Посчитать частоты символов первой строки.

Посчитать частоты символов второй строки.

Сравнить таблицы.

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

Python (через Counter)

Смысл Counter: это готовая частотная таблица для хешируемых элементов.

Документация: collections.Counter

!Схема: анаграммы проверяются сравнением частот символов

Важная деталь: размер алфавита

Если строка состоит только из маленьких английских букв, можно использовать массив из 26 чисел вместо hash map. На LeetCode это часто ускоряет решение и снижает память, но паттерн остаётся тем же: ключ становится индексом буквы.

Hash map остаётся универсальным вариантом, когда:

алфавит большой (Unicode)

символы могут быть любыми

элементы — не только символы, но и слова, числа, пары значений

Группировка анаграмм

Пример задачи: Group Anagrams

Здесь нужно сгруппировать слова так, чтобы анаграммы оказались в одной группе. Это почти всегда решают через «подпись» (каноническое представление), которая одинакова у всех анаграмм.

Есть два популярных варианта подписи:

Отсортированная строка

- ключ: "".join(sorted(word)) - плюс: просто - минус: сортировка стоит дороже линейного подсчёта

Частотный вектор

- ключ: кортеж из 26 чисел (для a..z) или другой фиксированной длины - плюс: линейно по длине слова - минус: требует аккуратной сборки ключа

Python: группировка по отсортированному ключу

Что здесь делает hash map:

ключ: подпись группы

значение: список слов в группе

Частоты как инструмент для «majority» и «топ по частоте»

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

Пример задачи: Sort Characters By Frequency

Общий план:

Посчитать freq.

Отсортировать элементы по count или использовать структуру типа кучи.

Важно: частотная таблица отвечает за быстрое накопление статистики. Дальше вы выбираете подходящую «вторую фазу» в зависимости от требования задачи.

Частые ошибки и как их избегать

Забыли про значение по умолчанию

- в Python используйте get(key, 0) или defaultdict(int) - в Java используйте getOrDefault

Сравнивают анаграммы по множеству, а не по частоте

- множества учитывают только факт присутствия - анаграммы требуют совпадения количеств

Неверный тип ключа

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

Пытаются решить «первый уникальный» одним проходом

- чаще всего нужен второй проход по исходному порядку

Мини-чек-лист перед решением задач на counting

Определите, что считается элементом: число, символ, слово, пара.

Выберите значение: чаще всего count, иногда список индексов.

Решите, нужна ли вторая фаза: второй проход, сортировка, куча.

Проверьте, не проще ли использовать фиксированный массив вместо map, если алфавит маленький.

Что дальше

Частотные таблицы закрывают задачи про counting, анаграммы и уникальность. Следующий крупный пласт задач с hash map обычно связан с поиском условий по сумме и индексам (например, хранить значение → индекс), а также с комбинированием hash map и других техник, вроде префиксных сумм и скользящего окна.

Поиск пар и дополнений: Two Sum и похожие задачи

Задачи класса Two Sum — один из самых частых способов применить ассоциативные массивы на LeetCode. Если в прошлых статьях мы использовали hash map как частотную таблицу (элемент счётчик), то здесь мы используем его как структуру для быстрого ответа на вопрос «видели ли мы уже нужное дополнение?».

Ключевая идея: вместо перебора всех пар за мы делаем один проход по массиву и поддерживаем hash map, который позволяет проверять «дополнение» в среднем за . В итоге типичная асимптотика становится по времени и по памяти.

Ссылки на канонические задачи:

Two Sum

Two Sum II - Input Array Is Sorted

Pairs of Songs With Total Durations Divisible by 60

Паттерн «дополнение до цели»

Пусть дано nums и target. Для текущего числа x нам нужен партнёр y, такой что x + y = target. Значит:

искомое дополнение: need = target - x

Если мы уже встречали need раньше, то пара найдена.

Что хранить в hash map

Зависит от того, что требует задача:

нужно вернуть индексы пары: храните value -> index

нужно вернуть существование пары: достаточно value -> True (или set)

нужно посчитать количество пар: храните value -> count

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

!Блок-схема «однопроходного» решения Two Sum через проверку дополнения и запись в словарь

Two Sum: возврат индексов

В задаче Two Sum нужно вернуть индексы двух разных элементов.

Однопроходный шаблон

Алгоритм:

Создаём пустой словарь seen.

Идём слева направо.

Для каждого x считаем need = target - x.

Если need уже есть в seen, возвращаем пару индексов.

Иначе записываем текущий элемент в seen.

Почему запись делается после проверки:

так мы гарантируем, что не используем один и тот же элемент дважды

это важно, когда target = 2 * x и в массиве встречается x

Python

Частые тонкости

Дубликаты значений

Если число встречается несколько раз, перезапись seen[x] = i меняет индекс на последний. Для классического Two Sum это обычно не проблема, потому что вы вернёте ответ при первом найденном дополнении.

Возврат именно первых индексов

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

Если нужно только проверить существование пары

Можно использовать set, потому что индексы не нужны.

Two Sum: «существует ли пара»

Если от вас требуется только true/false, структура упрощается:

seen как множество значений

проверяем need in seen

Python-идея:

В этом варианте вы тренируете тот же паттерн «дополнение», просто значение в map больше не несёт полезной нагрузки.

Подсчёт количества пар: когда нужны частоты

Следующая типовая вариация: посчитать число пар, удовлетворяющих условию.

Здесь почти всегда нужен счётчик, то есть возврат к идеям из статьи про частотные таблицы:

freq[value] = сколько раз value уже встречалось слева

Шаблон для подсчёта пар с суммой target

Идём слева направо:

для текущего x количество новых пар равно freq[target - x] (если такое значение встречалось)

затем увеличиваем freq[x]

Важно: сначала считаем вклад, потом увеличиваем частоту, иначе можно ошибиться и «спарить» элемент с самим собой в рамках одной позиции.

Python-идея:

Вариации паттерна «дополнение»

Дополнение по модулю

В задачах вроде Pairs of Songs With Total Durations Divisible by 60 условие выглядит как:

(a + b) % 60 == 0

Тогда вместо target - x вы работаете с остатками:

r = x % 60

нужный остаток: need = (60 - r) % 60

ответ увеличивается на freq[need]

Это тот же Two Sum, только «цель» задаётся на остатках.

Two Sum на отсортированном массиве

В Two Sum II - Input Array Is Sorted вход уже отсортирован. Там часто выгоднее применить два указателя:

левый индекс l и правый r

если сумма мала, двигаем l вправо

если сумма велика, двигаем r влево

Hash map тоже решит задачу за , но два указателя дадут:

по времени

по памяти

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

«Разность равна k» и другие преобразования

Иногда формулировка звучит как:

найти пару, где a - b = k

Это тоже превращается в дополнение:

для текущего a вам нужен b = a - k

Вы по-прежнему проверяете наличие нужного значения в map или set.

Типовые ошибки

Сохранить элемент в map до проверки дополнения

Это может привести к использованию одного и того же элемента дважды, особенно при target = 2 * x.

Путать, что хранить: индекс или частоту

- индексы нужны, чтобы вернуть позиции - частоты нужны, чтобы корректно считать количество пар

Не учитывать дубликаты, когда требуется подсчёт

Если нужно число пар, то set недостаточен: он «схлопывает» повторы.

Игнорировать условие задачи про вход

Если вход отсортирован, возможно, хеш-таблица не нужна: два указателя дают по памяти.

Мини-чек-лист перед решением задач про пары

Определите, что вам нужно на выходе:

- индексы - факт существования - количество пар

Запишите, как выражается «партнёр» через текущий элемент:

- need = target - x - или need = (M - (x % M)) % M

Выберите структуру:

- dict для value -> index - set для существования - dict/Counter/defaultdict(int) для частот

Проверьте порядок действий:

- обычно сначала проверка, потом запись/инкремент

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

Префиксные суммы + map: подмассивы с заданной суммой

Первые статьи курса показали два базовых применения ассоциативных массивов:

частотные таблицы (элемент сколько раз встретился)

поиск дополнения (значение видели ли раньше/где видели) в стиле Two Sum

Теперь соберём эти идеи в один из самых мощных паттернов LeetCode: префиксные суммы + hash map для задач вида «сколько подмассивов имеет сумму ?» или «существует ли подмассив с таким свойством?».

Каноническая задача:

Subarray Sum Equals K

Что такое префиксная сумма

Пусть дан массив nums.

Префиксная сумма на позиции i — это сумма первых i элементов.

Обычно удобно определять так:

(сумма «нулевых» элементов)

для

Тогда сумма подмассива nums[l..r] выражается через разность префиксов:

Что означает каждая часть формулы:

— сумма элементов от nums[0] до nums[r]

— сумма элементов от nums[0] до nums[l-1]

разность «отсекает» всё до l и оставляет ровно сумму l..r

!Иллюстрация связи суммы подмассива с разностью префиксных сумм

Как из подмассива сделать Two Sum

Хотим посчитать количество подмассивов с суммой k.

Условие:

Переносим:

Интерпретация:

мы идём слева направо и считаем текущий префикс curr = prefix[r+1]

чтобы получить подмассив суммы k, нам нужно найти, сколько раз раньше встречался префикс со значением curr - k

Это буквально паттерн «дополнение до цели» из статьи про Two Sum, только теперь:

«значения» — это префиксные суммы

«частоты» — это сколько раз каждая префиксная сумма уже встречалась

Что хранить в map

Для задачи Subarray Sum Equals K нужно посчитать количество подмассивов, поэтому храним:

ключ: значение префиксной суммы

значение: сколько раз этот префикс встречался

То есть это снова частотная таблица, как во второй статье курса, но частоты считаются не для элементов массива, а для префиксных сумм.

Базовый алгоритм: Subarray Sum Equals K

Идея в одном проходе:

Заводим freq для частот префиксных сумм.

Очень важно: кладём freq[0] = 1.

Поддерживаем текущую сумму curr.

Для каждого элемента x:

- curr += x - добавляем к ответу freq[curr - k] (сколько подходящих prefix[l] уже было) - увеличиваем freq[curr]

Почему freq[0] = 1 обязательно:

это означает, что «пустой префикс» (до начала массива) уже встречался один раз

благодаря этому корректно учитываются подмассивы, которые начинаются с индекса 0

Python

Java

Почему это работает даже с отрицательными числами

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

увеличение правой границы всегда увеличивает сумму

увеличение левой границы всегда уменьшает сумму

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

Префиксные суммы + map не требуют монотонности. Мы просто считаем:

сколько раз ранее была сумма curr - k

И это корректно независимо от знаков элементов.

Тонкости, которые часто ломают решение

Неправильный порядок действий

- правильно: сначала ans += freq[curr - k], потом freq[curr] += 1 - иначе можно некорректно учитывать подмассив «нулевой длины» в некоторых вариантах задач и ошибиться на случаях с k = 0

Забыли инициализировать freq[0] = 1

- потеряете все подмассивы, начинающиеся с 0

Пытаются хранить индекс, а не частоту

- в этой задаче нужно количество подмассивов - один и тот же префикс может встречаться много раз, и каждая встреча даёт новые подмассивы

Сложность

Временная сложность:

- один проход по массиву - операции со словарём в среднем (см. первую статью курса)

Память: в худшем случае

- если все префиксные суммы разные

Вариации паттерна на LeetCode

Подмассивы, сумма которых кратна

Задачи вида: найти количество (или факт существования) подмассивов, для которых сумма делится на k.

Классический пример:

Subarray Sums Divisible by K

Ключевая идея:

если два префикса дают одинаковый остаток по модулю k, то их разность делится на k

То есть вместо prefix как ключа используем:

rem = prefix % k

map считает частоты остатков

Важная деталь по языкам:

в некоторых языках остаток от отрицательного числа может быть отрицательным

поэтому остаток часто нормализуют в диапазон 0..k-1 (например, в Java: ((rem % k) + k) % k)

«Самый длинный подмассив с суммой k»

Иногда просят не количество, а длину максимального подмассива с суммой k. Тогда map обычно хранит:

ключ: префиксная сумма

значение: самый ранний индекс, где она встретилась

Логика похожа, но вместо частот нам важно «как можно дальше растянуть» подмассив.

Мини-чек-лист перед решением задач на префиксы + map

Понимаете, что сумма подмассива — это разность двух префиксных сумм.

Умеете превращать условие в «найти, сколько раз встречался curr - need».

Правильно выбираете, что хранить в map:

- количество подмассивов: prefix -> count - максимальная длина: prefix -> earliest index

Не забываете freq[0] = 1 для задач на количество.

Помните, что метод работает с отрицательными числами, в отличие от многих решений со скользящим окном.

Группировка и индексирование: buckets, списки по ключу

Ассоциативные массивы на LeetCode используют не только для частот и дополнений (Two Sum), но и как универсальный инструмент организации данных по признаку.

В прошлых статьях мы уже встречали две «роли» hash map:

частотная таблица: элемент -> сколько раз встретился

проверка дополнения / запоминание факта: значение -> видели ли/где видели

Теперь добавим третью роль, которая постоянно появляется в задачах: группировка и индексирование.

Группировка: ключ группы -> список элементов группы

Индексирование: ключ -> список позиций (индексов), где ключ встретился

Buckets (корзины): числовой ключ (частота/размер/категория) -> список элементов или даже массив списков, где индекс массива и есть ключ

Базовая идея: map как «много-значное» отображение

Обычный словарь хранит одно значение на ключ. Но во многих задачах нужно хранить много значений для одного ключа.

Тогда значение в map делают контейнером:

key -> list (самый частый вариант)

key -> set (если важна уникальность)

key -> queue/deque (если важен порядок извлечения)

Ключевой паттерн: для каждого элемента вычисляем ключ и добавляем элемент в контейнер по этому ключу.

!Как элементы раскладываются по группам в map, где значение — список

Группировка: ключ -> список элементов

Когда это нужно

Сигналы в задачах:

«сгруппировать по …» / group by

«вернуть группы»

«собрать все элементы с одинаковым признаком»

Классические примеры на LeetCode:

Group Anagrams — ключом выступает «подпись» анаграммы

Find Duplicate File in System — ключом выступает содержимое файла, значением список путей

Шаблон (Python): defaultdict(list)

Здесь важно понимать роли:

key — вычисляемый признак группировки

groups[key] — список, куда мы добавляем элементы

Аналоги шаблона по языкам

#### Java: computeIfAbsent

computeIfAbsent означает: если ключа ещё нет, создать новый список и положить его в map.

#### C++: unordered_map<Key, vector<Value>>

#### JavaScript: Map и массивы

Индексирование: значение -> список индексов

Иногда нужно не сгруппировать сами значения, а быстро отвечать на запросы вида:

«где встречается x?»

«какие позиции у x?»

Тогда строят инвертированный индекс:

ключ: значение (например, число или строка)

значение: список индексов, где оно встречалось

Это особенно полезно, если после построения индекса будут множественные запросы.

Пример: собрать позиции всех значений

Где это встречается на LeetCode

Group the People Given the Group Size They Belong To — удобная реализация использует groupSize -> список людей, а затем «срезает» списки на готовые группы

Buckets: «корзины» по числовому ключу

Слово bucket на практике означает одно из двух:

bucket как значение в map: key -> list (мы уже это делаем)

bucket sort как массив корзин: buckets[i] хранит список элементов, у которых «оценка» равна i

В задачах про частоты (топ-K, сортировка по частоте) второй вариант часто даёт простой и быстрый код.

Связь с частотной таблицей

В статье про counting мы строили freq: element -> count. Buckets добавляют второй слой:

сначала считаем freq

затем «переворачиваем» по частоте: count -> список элементов

То есть получается:

частотная таблица: element -> count

корзины: count -> [elements]

!Как из freq строятся корзины buckets по частоте

Пример: Top K Frequent Elements через buckets

Задача: Top K Frequent Elements

Идея buckets:

максимальная частота не превышает (длины массива)

создаём массив buckets длины n + 1

для каждого элемента x с частотой c кладём x в buckets[c]

обходим buckets с конца, собирая ответ

Python:

Что здесь важно:

buckets — это не hash map, но это продолжение идеи «группировка по ключу», где ключ — целое число от 1 до n

такой приём часто заменяет сортировку по частоте

Как выбрать ключ и что хранить в списке

Решение обычно сводится к двум вопросам.

Что является «группой»?

- анаграммы: ключ = подпись (например, отсортированная строка) - диагонали матрицы: ключ = r - c - люди с размером группы: ключ = groupSize - частота: ключ = count

Что нужно вернуть или что пригодится дальше?

- вернуть сами элементы: храните элементы - вернуть индексы: храните индексы - нужно быстрее удалять/проверять уникальность: храните set

Сложность

Обычно для n элементов:

время: на один проход и распределение по корзинам (операции map в среднем )

память: , потому что суммарно вы храните все элементы (или все индексы) внутри списков

У buckets-массива:

память: на массив корзин плюс элементы

время: на построение плюс обход корзин (в сумме тоже )

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

Не инициализировали контейнер для нового ключа

- симптом: ошибка доступа или KeyError - лечение: defaultdict(list), computeIfAbsent, явная проверка if key not in map

Перепутали, что хранить: элемент или индекс

- если на выходе нужны позиции, не храните значения (и наоборот)

Использовали set, когда нужен порядок или дубликаты

- set уничтожает повторы и не гарантирует исходный порядок

Слишком «тяжёлый» ключ

- если ключ строится сортировкой строки, это может быть дороже, чем подсчёт частот - если ключом можно сделать фиксированный кортеж/вектор, часто это быстрее

Как это связывается с предыдущими паттернами

Как и в counting, мы часто делаем один проход и наполняем структуру вида ключ -> значение.

Как и в Two Sum / префиксах, важно правильно выбрать, что именно хранить: факт, индекс, частоту или список.

Buckets часто строятся поверх частотной таблицы и дают удобную альтернативу сортировке.

Эта техника завершает базовый «набор ролей» hash map на LeetCode: считать, искать дополнение, группировать и индексировать. Дальше эти роли начинают комбинироваться с другими подходами (скользящее окно, два указателя, heap) в более комплексных задачах.

Скользящее окно с hash map: подстроки и ограничения частот

Скользящее окно (sliding window) — один из самых частых паттернов на LeetCode для задач про подстроки и подмассивы, где требуется поддерживать условие на текущий непрерывный отрезок.

Связь с предыдущими статьями курса прямая:

из статьи про частотные таблицы мы берём идею элемент -> count, только считаем частоты внутри окна, а не во всём массиве

из статьи про Two Sum мы берём дисциплину одного прохода и обновления структуры данных на лету

в отличие от статьи про префиксные суммы, здесь мы не фиксируем правую границу раз и навсегда, а двигаем обе границы, сохраняя инвариант

Что такое скользящее окно

Окно — это отрезок [l..r] (или полуинтервал l, r)), который мы перемещаем по строке/массиву.

Типовая схема:

расширяем окно вправо (двигаем r)

обновляем структуру данных по добавленному элементу

если условие нарушено, сжимаем окно слева (двигаем l), откатывая влияние элементов

![Иллюстрация движения границ окна и поддержки частот в hash map

Почему здесь нужен hash map

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

“все символы в окне уникальны”

“в окне не более K различных значений”

“окно должно содержать все символы строки t с нужными количествами”

Для этого удобно держать freq:

ключ: элемент (символ/число)

значение: сколько раз элемент сейчас находится в окне

Это буквально частотная таблица, но динамическая.

Ключевая идея: инвариант окна

Почти все задачи со скользящим окном держатся на инварианте.

Инвариант — это условие, которое мы стараемся поддерживать после сжатия окна.

Чаще всего встречаются два семейства задач:

“не более” (at most): поддерживаем условие “окно валидно”, при нарушении сжимаем слева

“минимальное валидное окно”: расширяем, пока не станет валидно, затем сжимаем, пока валидность не потеряется, фиксируя лучший ответ

Базовый шаблон: “at most”

Примеры задач:

Longest Substring Without Repeating Characters

Fruit Into Baskets

Longest Substring with At Most K Distinct Characters (премиум)

Общая структура

Мы расширяем r, добавляя элемент в freq, и пока окно “плохое”, двигаем l, уменьшая частоты.

Python-скелет (для массива/строки):

Зачем удалять ключи с нулём

Во многих условиях важно число различных элементов, например len(freq).

Если не удалять ключи с нулевой частотой:

len(freq) будет неверным

логика “сколько различных в окне” сломается

Пример паттерна: “не более K различных”

Условие окна:

валидно, если distinct <= K, где distinct = len(freq)

Тогда window_is_bad(freq) — это len(freq) > K.

Это один из самых полезных “строительных блоков” на LeetCode.

“Ровно K различных” через разность двух “at most”

Иногда задача просит количество подмассивов/подстрок с ровно K различными.

Классический пример:

Subarrays with K Different Integers

Стандартная техника:

посчитать atMost(K)

посчитать atMost(K-1)

ответ — разность

Формула:

Пояснение каждого элемента:

— количество подмассивов, где различных элементов не больше

— количество подмассивов, где различных не больше

разность оставляет только те, где различных ровно , потому что все случаи с вычитаются

Важно: это работает именно для “ровно K различных”, потому что множество подмассивов с является подмножеством .

Минимальное окно: частотные ограничения “должно содержать t”

Пример задачи:

Minimum Window Substring

Здесь условие не про “уникальность”, а про покрытие:

у нас есть строка t

окно в s валидно, если содержит все символы t в нужных количествах

Что хранить в map

need[c] — сколько раз символ c должен встретиться (частоты t)

window[c] — сколько раз c сейчас в окне

Как быстро проверять валидность

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

Стандартный трюк:

required = len(need) — сколько разных символов нужно удовлетворить

formed — сколько разных символов сейчас удовлетворены, то есть window[c] >= need[c]

Тогда:

окно валидно, если formed == required

Высокоуровневый алгоритм

расширяем r, увеличивая window

когда окно стало валидным (formed == required), пытаемся сжать слева, улучшая ответ

как только валидность потеряли, снова расширяем

Ещё один частый вариант: “ограничение на количество плохих элементов”

Иногда условие звучит не как “K различных”, а как “можно исправить не более K”.

Пример:

Longest Repeating Character Replacement

Идея окна:

хотим, чтобы окно можно было превратить в строку из одного повторяющегося символа

цена превращения равна window_len - max_freq, где max_freq — максимальная частота одного символа в окне

окно допустимо, если window_len - max_freq <= k

Здесь hash map нужен, чтобы обновлять частоты символов при движении границ.

Важное практическое замечание для этой задачи:

max_freq часто ведут как “максимум, который мы когда-либо видели при расширении”, и при сжатии окна его не уменьшают

это работает из-за устройства условия и того, что мы ищем максимум длины, но этот момент легко перепутать, поэтому полезно отдельно понимать инвариант и доказательство корректности

Как понять, что задача — на sliding window + map

Хорошие “сигналы”:

дан массив/строка и речь про подотрезок/подстроку

надо найти самую длинную/самую короткую подстроку с ограничением

есть ограничение вида:

- “не более K” - “все уникальны” - “содержит все символы/слова с частотами”

Если ограничения выражаются через частоты внутри отрезка, hash map почти всегда будет в решении.

Типовые ошибки

забывают уменьшать частоты при сжатии окна

не удаляют ключ при freq[x] == 0 и получают неверное число различных

пытаются делать sliding window там, где нет монотонности условия (например, “сумма ровно k” с отрицательными числами обычно не решается окном и требует префиксов + map из предыдущей статьи)

смешивают роли словаря:

- для окна почти всегда нужно именно элемент -> count, а не элемент -> индекс

Мини-чек-лист перед написанием решения

Что является окном: подстрока s[l..r] или подмассив nums[l..r].

Какой инвариант окна: “at most”, “минимальное покрывающее”, “не более K нарушений”.

Что хранит hash map:

- element -> count внутри окна - иногда плюс need для “покрытия”

Как понять, что окно стало плохим и как его чинить: условие для while.

Нужно ли удалять нулевые частоты (если используете len(freq) или аналоги).

Эта техника завершает базовый набор паттернов для hash map в задачах LeetCode: мы умеем считать частоты глобально, искать дополнение, работать с префиксами, группировать, и теперь — поддерживать частоты локально в движущемся окне.

Оптимизация и ловушки: коллизии, память, edge cases

Hash map в задачах LeetCode почти всегда даёт линейное решение там, где прямой перебор даёт квадратичное. Но после того, как вы освоили основные паттерны курса (counting, Two Sum, префиксы, группировка, sliding window), начинает решать не только идея, но и детали: коллизии, память, выбор ключа, порядок обновления, краевые случаи.

Эта статья собрана как практический список того, что чаще всего ломает решения или делает их заметно медленнее.

Коллизии и сложность: почему иногда «не »

Мы уже говорили, что операции словаря обычно считают в среднем. Это означает:

в среднем вставка/поиск/обновление занимают константное время

в худшем случае возможна деградация

Что такое коллизия и почему она важна

Коллизия возникает, когда разные ключи попадают в одно и то же место внутренней таблицы. Тогда структуре нужно различать эти ключи дополнительными действиями.

На LeetCode обычно достаточно стандартного допущения про средний случай, но помнить про коллизии полезно для двух ситуаций:

вы используете плохой ключ (например, огромные строки, тяжёлая сериализация состояния)

вы храните слишком много элементов и словарь часто расширяется

Rehash и амортизация

При росте количества элементов hash map увеличивает внутренний буфер и перераскладывает элементы. Это делает отдельные операции вставки «дорогими», но в среднем на длинной последовательности вставок получается хорошая оценка.

Если вам нужно объяснить это в терминах сложности:

амортизированное означает, что суммарное время на операций примерно пропорционально

!Иллюстрация коллизий и переразмещения элементов при расширении таблицы

Практический вывод для LeetCode

Не пытайтесь «переоптимизировать» из страха худшего случая, если задача стандартная.

Оптимизируйте там, где это реально влияет: ключи, память, количество операций со словарём, удаления в sliding window.

Память: скрытая цена словаря

В решениях часто пишут: Time , Space . Это верно, но у словаря большая константа по памяти.

Где память «взрывается» чаще всего

группировка: key -> list, где суммарно во всех списках лежит почти весь вход

индексация: value -> list of indices при большом числе повторов

префиксные суммы: в худшем случае все префиксы разные, и map вырастает до размера

ключи-строки: если вы делаете ключи через конкатенации и сортировки, вы можете хранить много крупных строк

Быстрые способы снизить память

Если область значений маленькая, заменяйте map на массив.

- пример: частоты букв a..z лучше хранить в массиве из 26 чисел

Не храните списки индексов, если вам достаточно только частоты или факта существования.

В группировке анаграмм при маленьком алфавите предпочитайте ключ-частотный вектор (например, кортеж из 26 чисел), а не отсортированную строку, если сортировка и память критичны.

Выбор ключа: скорость и корректность

Ключ должен быть одновременно:

однозначным для вашей логики

хешируемым в вашем языке

не слишком тяжёлым для вычисления

Типовые ошибки выбора ключа

Использовать изменяемый объект как ключ.

- пример: в Python list нельзя использовать как ключ, а в JavaScript объект как ключ в обычном {} приводит к неожиданным преобразованиям

Делать ключ слишком дорогим.

- пример: ключ для анаграмм через сортировку слова создаёт новую строку и стоит дороже, чем линейный подсчёт

Делать ключ неоднозначным при сериализации.

- пример: склеивать числа в строку без разделителя: "1" + "23" и "12" + "3" дают одинаковую строку

Хорошие практики

Для составного состояния используйте кортеж/пару.

- Python: (a, b) - Java: собственный класс с hashCode/equals или строковый ключ с безопасным разделителем

Если делаете строковый ключ, используйте разделитель, который точно не встречается в данных, или кодируйте длины.

Полезные справки по реализациям:

Python dict

Java HashMap

C++ unordered_map

JavaScript Map

Edge cases в ключевых паттернах курса

Ниже собраны самые частые «краевые случаи», которые дают WA (wrong answer) даже при правильной основной идее.

Частотные таблицы

Частый edge case: пустой вход

Проверьте, что ваш код корректно работает при:

пустой строке

пустом массиве

Обычно это означает:

корректную инициализацию

отсутствие обращения к элементам без проверки

Частый edge case: сравнение «как множества» вместо «как частот»

Для анаграмм нельзя сравнивать set(s) == set(t), потому что множества игнорируют количества.

Правильно:

char -> count

Two Sum и «дополнение»

Порядок действий: сначала проверка, потом запись

Чтобы не использовать один и тот же элемент дважды, классический порядок такой:

посчитать need

проверить need in seen

записать текущий элемент

Если записать сначала, то на кейсах вида target = 2*x можно получить неправильную пару.

Дубликаты: что хранить

если нужно вернуть индексы, храните value -> index

если нужно посчитать число пар, храните value -> count

если нужен только факт существования, используйте set

Ошибка: использовать set, когда задача просит количество пар.

Префиксные суммы + map

Edge case: забыли freq[0] = 1

Для задачи на количество подмассивов с суммой важно считать «пустой префикс» как уже встреченный один раз. Иначе вы потеряете все подмассивы, начинающиеся с позиции 0.

Edge case: порядок обновления

Правильный порядок для подсчёта количества:

обновить текущую сумму curr

добавить к ответу freq[curr - k]

увеличить freq[curr]

Если поменять местами пункты 2 и 3, в некоторых вариантах задач можно получить лишние подсчёты.

Edge case: модуль и отрицательные числа

В задачах вида «сумма подмассива делится на » вы часто храните остатки. Проблема в том, что остаток от отрицательных чисел в некоторых языках может быть отрицательным.

Практика:

нормализуйте остаток в диапазон 0..k-1

Группировка и buckets

Edge case: забыли инициализировать список для нового ключа

Это классическая ошибка для key -> list. Решение:

Python: defaultdict(list)

Java: computeIfAbsent

JS: явная проверка has

Edge case: buckets размером не

В задачах вроде Top K Frequent частота элемента может быть до , поэтому buckets обычно делают размера n + 1.

Ошибка: сделать buckets = [[] for _ in range(n)] и получить выход за границы на частоте n.

Sliding window + hash map

Edge case: не удалять ключи с нулевой частотой

Если ваше условие использует число различных элементов, например len(freq), то при уменьшении счётчика до нуля ключ нужно удалить.

Иначе:

словарь будет «помнить» элементы, которых уже нет в окне

условие distinct <= K начнёт работать неправильно

Edge case: неправильный инвариант

Sliding window работает, когда вы умеете поддерживать условие через монотонное «чинится сдвигом левой границы».

Типичная ошибка:

пытаться решать «сумма ровно » скользящим окном при наличии отрицательных чисел

В таких задачах чаще нужен паттерн из статьи про префиксы.

Микрооптимизации, которые действительно помогают

Снижайте число обращений к map

не вычисляйте один и тот же ключ несколько раз

вытаскивайте значение один раз в локальную переменную, если язык и стиль позволяют

Используйте правильную структуру под задачу

set, если не нужны значения

массив, если ключи из малого диапазона

Counter/defaultdict(int), если считаете частоты

Учитывайте стоимость ключа

В некоторых задачах ключ доминирует над всеми остальными действиями:

сортировка строк для ключа анаграммы

сериализация состояния в строку

Если ключ дорогой, вы можете формально иметь проход, но с тяжёлой константой, которая и даёт TLE.

Итоговый чек-лист перед отправкой решения

Проверьте, что вы правильно выбрали роль словаря:

- element -> count - value -> index - prefix -> count - key -> list

Проверьте порядок обновления, если вы считаете количество (пары, подмассивы).

Проверьте обязательные инициализации:

- freq[0] = 1 в задачах на количество подмассивов по префиксам

Проверьте edge cases:

- пустой вход - отрицательные числа (особенно при модуле) - дубликаты

Проверьте, не держите ли вы лишние данные в значении map (список индексов вместо счётчика).

Эта статья завершает курс «Ассоциативные массивы в задачах LeetCode» с практической стороны: после освоения паттернов именно такие детали чаще всего отделяют «почти правильное» решение от стабильного AC на всех тестах.