Быстрый поиск: set и map

Хеш-множество особенно полезно, когда текущему элементу нужен партнёр среди уже просмотренных. Вместо перебора всех прошлых позиций мы формулируем один ключ, который хотим найти.

Как найти два разных индекса с нужной суммой

Дан массив целых чисел и число target. Нужно определить, существуют ли два разных индекса, значения на которых в сумме дают target. Возвращать сами индексы пока не требуется.

Сколько пар проверяет прямое решение

Проверить каждую пару i < j и сравнить values[i] + values[j] с целью. Это корректно и требует O(n²) времени в случае без ответа. Дополнительная память не нужна.

Почему весь префикс не нужен для партнёра

Для текущего x нас интересует только одно значение партнёра: target - x. Перебор сравнивает x со всем префиксом, хотя можно сразу спросить, встречалось ли нужное дополнение.

Вычисляем единственное требуемое дополнение

Если один элемент пары равен x, второй обязан равняться target - x. Храним множество прошлых значений и проверяем дополнение за ожидаемое O(1).

Какие позиции представлены в seen

Перед обработкой позиции i множество seen содержит значения строго левее i. Поэтому успешная проверка target - values[i] гарантирует существование другого индекса. После неуспешной проверки добавляем текущее значение и восстанавливаем инвариант для следующего шага.

Ищем партнёра до вставки текущего значения

1. Создать пустое множество seen.
2. Для текущего value вычислить complement = target - value.
3. Если complement находится в seen, вернуть true.
4. Иначе добавить value в seen.
5. После полного прохода вернуть false.

Проверка выполняется до вставки: так пара (3, 3) требует двух реальных троек, а не одного элемента, использованного дважды.

Хеш-поиск пары с безопасной суммой

C++17

#include <cassert>
#include <unordered_set>
#include <vector>

using namespace std;

bool hasPairWithSum(const vector<int>& values, long long target) {
    unordered_set<long long> seen;

    for (int value : values) {
        const long long complement = target - value;
        if (seen.find(complement) != seen.end()) {
            return true;
        }
        seen.insert(value);
    }

    return false;
}

int main() {
    assert(hasPairWithSum({2, 7, 11, 15}, 9));
    assert(hasPairWithSum({3, 3}, 6));
    assert(!hasPairWithSum({3}, 6));
    assert(!hasPairWithSum({1, 2, 4}, 8));
}

Python 3

def has_pair_with_sum(values: list[int], target: int) -> bool:
    seen: set[int] = set()

    for value in values:
        complement = target - value
        if complement in seen:
            return True
        seen.add(value)

    return False


assert has_pair_with_sum([2, 7, 11, 15], 9)
assert has_pair_with_sum([3, 3], 6)
assert not has_pair_with_sum([3], 6)
assert not has_pair_with_sum([1, 2, 4], 8)

Средняя цена поиска дополнения

При ожидаемом O(1) для операций хеш-множества весь алгоритм работает за ожидаемое O(n) и хранит до n ключей, то есть использует O(n) памяти. В C++ цель и ключи представлены long long, чтобы вычитание не переполнило int при обычных 32-битных входах.

Как ключ превращается в место хранения

Хеш-функция преобразует ключ в целое хеш-значение. По нему таблица выбирает корзину (bucket) или стартовую позицию внутреннего массива. Это не «магический адрес»: разные ключи могут попасть в одно место. Такое совпадение называется коллизией, и корректная таблица обязана отличить ключи дополнительной проверкой равенства.

Для пользовательского типа должны быть согласованы два правила: если ключи равны, их хеши обязаны совпадать. Обратное неверно: одинаковый хеш ещё не доказывает равенство.

Два способа пережить коллизию

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

Это две модели для понимания, а не обещание конкретной внутренней реализации unordered_map, dict или set. Публичный контракт контейнера важнее детали версии языка.

Load factor связывает скорость и память

Коэффициент заполнения (load factor) сравнивает число записей с числом доступных корзин или позиций. При слишком плотной таблице коллизий становится больше. Тогда контейнер увеличивает внутренний массив и выполняет rehash: заново распределяет существующие ключи.

Обычная операция ожидаемо занимает O(1), но отдельная вставка с rehash может потребовать O(n). Таблица также расходует больше памяти, чем сами пары ключ–значение: нужны пустые позиции, служебные метки или ссылки цепочек.

Почему O(1) у хеша ожидаемое, а не безусловное

При хорошем распределении средняя корзина мала, поэтому число сравнений не растёт вместе с n. Но множество коллизий, плохая хеш-функция или специально подобранные ключи могут собрать длинную цепочку и ухудшить одну операцию до O(n).

Если нужны гарантированные логарифмические границы и упорядоченный обход ключей, в C++ сравните unordered_map с map: у map поиск, вставка и удаление требуют O(log n), зато ключи идут по порядку. Python dict сохраняет порядок вставки как часть языкового поведения, но этот порядок не является сортировкой ключей.

Карта, множество или прямой массив

• set / unordered_set: нужен только факт принадлежности или устранение дублей;
• dict / unordered_map: с ключом связано значение — частота, индекс, группа;
• массив счётчиков: ключи — плотные небольшие целые числа;
• упорядоченная структура: нужны минимум, следующий ключ или обход по сортировке.

Хеширование особенно естественно для частот, группировки, дедупликации и поиска дополнения в Two Sum. Оно не помогает само по себе, если запрос зависит от порядка, диапазона ключей или ближайшего соседа.

Равные значения, отрицательные числа и переполнение

• Меньше двух элементов: ответ всегда false.
• target чётный и нужен партнёр target / 2: требуются два вхождения.
• Ноль и отрицательные значения обрабатываются тем же правилом дополнения.
• Ответ может появиться в самом конце.
• Очень большие значения требуют типа, в котором безопасно вычисляется разность.

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

Проверь обычную пару [2, 7], две равные позиции [3, 3], одну тройку [3], отсутствие ответа и смесь отрицательных чисел, например [-4, 9, 1] с целью 5.

Когда партнёр выражается формулой

Сигналы: нужна пара, для текущего элемента можно однозначно вычислить требуемого партнёра, а ответ разрешено искать среди уже просмотренного префикса. Формула часто выглядит как partner = target - current.

Когда нужны индексы, частоты или два указателя

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

Почему множество не возвращает позицию

Вопрос. Почему множество значений достаточно для ответа true/false, но не для возврата индексов?

Ответ. Множество сообщает только факт наличия ключа и не хранит связанную позицию. Для индексов нужен словарь значение → индекс.

Как один элемент создаёт ложную пару

Вопрос. Что произойдёт с [3], target = 6, если сначала добавить 3, а затем искать дополнение?

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

Возвращаем индексы вместо булева ответа

Верни индексы найденной пары или пустой результат. Подсказка: замени множество словарём value → earliestIndex; сначала ищи дополнение, затем сохраняй текущий индекс, не перезаписывая более ранний без необходимости.

Самостоятельная задача о первом совпадении

Задача 1

Даны две последовательности целых чисел. Верните первый по порядку элемент второй последовательности, который хотя бы раз встречается в первой, либо отсутствие результата. Входные последовательности изменять нельзя; приведите тесты с повторениями и пустыми входами.

Формула партнёра заменяет перебор префикса

Хеширование ускоряет не «поиск вообще», а конкретный повторяющийся вопрос: для текущего x за ожидаемое O(1) проверить наличие обязательного партнёра target - x в прошлом префиксе.