Хеш-таблицы: Two Sum и частоты

Хеш-таблица — главный инструмент для превращения O(n^2) в O(n).

Хеш-таблица (dict в Python) — структура данных, дающая вставку, удаление и поиск по ключу в среднем за O(1).

Two Sum за один проход

Дан неотсортированный массив и target. Для каждого элемента x нам нужен «дополнитель» target - x. Вместо вложенного цикла храним уже виденные числа в словаре: для каждого x проверяем, видели ли мы его дополнитель раньше.

def two_sum(arr, target):
    seen = {}
    for i, x in enumerate(arr):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i
    return [-1, -1]

print(two_sum([3, 2, 4], 6))
print(two_sum([3, 3], 6))
print(two_sum([1, 5, 9], 100))

Вывод:

[1, 2]
[0, 1]
[-1, -1]

Подсчёт частот

Очень частая подзадача — посчитать, сколько раз встречается каждый элемент. В стандартной библиотеке есть collections.Counter.

from collections import Counter

words = ["яблоко", "груша", "яблоко", "слива", "груша", "яблоко"]
freq = Counter(words)
print(dict(freq))
print(freq.most_common(1))

Вывод:

{'яблоко': 3, 'груша': 2, 'слива': 1}
[('яблоко', 3)]

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

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

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        key = "".join(sorted(w))
        groups[key].append(w)
    return list(groups.values())

print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))

Вывод:

[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

Как работает под капотом

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

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

Записывать seen[x] = i до проверки дополнителя — можно ошибочно вернуть один и тот же индекс дважды.
Использовать изменяемый объект (список) как ключ словаря — это ошибка.
Считать хеш-таблицу «всегда O(1)» и забывать про худший случай с коллизиями.

Итог

Хеш-таблица даёт поиск/вставку в среднем O(1).
Two Sum за один проход: ищем дополнитель среди уже виденных.
Counter и defaultdict из collections упрощают частоты и группировки.