Как узнать
пара с заданной суммой или разностью, дубликаты, подсчёт значений или любой вопрос «видел ли я это раньше?».
Как решать такие задачи
- Реши, что понадобится искать: партнёра, повтор, счётчик.
- Выбери ключ для поиска и что хранить вместе с ним: индекс, счётчик.
- Пройди вход один раз. Для каждого элемента сначала поищи то, что ему нужно.
- Потом сохрани элемент, чтобы его нашли следующие.
Вариант: Подсчёт
То же, но храним не где был элемент, а сколько раз он встретился. Подходит, когда важно, сколько каких элементов, а не где они стоят, например в анаграммах.
- Посчитай, что есть: словарь от элемента к числу его повторов. Для строчных латинских букв хватит и массива из 26 ячеек.
- Иди по тому, что нужно, и каждый раз снимай единицу. Счётчик ниже 0 — чего-то не хватает, и можно сразу остановиться.
- Два слова — анаграммы, если длины равны и все счётчики в конце равны 0. Чтобы сгруппировать анаграммы, дай каждому слову ключ, общий для всех его анаграмм, например отсортированные буквы, и собирай слова в словаре по этому ключу.
- Элемент большинства — та же идея: посчитай все значения и верни то, чей счётчик больше n / 2.
Где встречается
- Python. Словарь dict в Python — это хеш-таблица. В словарях Python ищет и переменные модуля, и атрибуты объектов, так что хеш-таблица работает почти в каждой строке программы.
- Redis. Redis хранит все ключи в хеш-таблице, поэтому значение по ключу находится сразу, сколько бы ключей ни было.
- Базы данных. Чтобы соединить две таблицы, PostgreSQL может сложить меньшую в хеш-таблицу по ключу, а потом пройти по большой и для каждой строки сразу найти пару. Это называется hash join.