Хеш-множества и словари для O(n)

Память вместо перебора

Самый частый приём ускорения на собеседовании — обменять память на скорость с помощью set или dict. Проверка «есть ли элемент в множестве» занимает в среднем O(1), тогда как поиск в спискеИзменяемая упорядоченная коллекция элементов: [1, 2, 3]. По-английски list. — O(n). Это превращает квадратичные решения в линейные.

Каноничный пример — задача Two Sum на неотсортированном массиве: для каждого числа проверяем, встречали ли мы уже его «дополнение» до target. Дополнения храним в словареКоллекция пар «ключ → значение»: {"a": 1}. Быстрый доступ по ключу. По-английски dict. «значение → индексНомер позиции элемента в последовательности. В Python нумерация с нуля: первый элемент — индекс 0.».

За один проход мы и заполняем словарь, и проверяем дополнение — итого O(n). Сравните с двойным циклом O(n²): на больших массивах разница колоссальна. И, в отличие от двух указателей, массив не нужно сортировать.

set для дубликатов и пересечений

set мгновенно отвечает на вопросы «есть ли дубликат?», «каковы общие элементы двух списков?». Это тоже паттерн: загнать данные в множествоКоллекция уникальных элементов без порядка: {1, 2, 3}. По-английски set. и пользоваться быстрым поиском.

Подсчёт частот через словарь

Словарь «элемент → счётчик» решает массу задач: самый частый символ, проверка анаграмм, группировка. В стандартной библиотеке для этого есть collections.Counter, но важно уметь и вручную.

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

⚠️ Частые ошибки новичков

Ошибка. Обратиться к несуществующему ключу словаря напрямую — counts[ch] += 1 без инициализации — это KeyError. Используйте dict.get(ch, 0) или collections.defaultdict(int). Запустите сломанный код и убедитесь в ошибке.