Паттерны быстрого поиска

Храни то, что понадобится искать снова

Один из главных алгоритмических паттернов с хеш-таблицей звучит так: если во время прохода приходится снова искать что-то среди уже просмотренных данных, попробуй сохранить эти данные в Set или Map. Дополнительная память часто превращает повторный линейный поиск в ожидаемую проверку за O(1).

Выбор структуры зависит от вопроса. Если достаточно знать, встречалось ли значение, подходит Set. Если вместе с ним нужно помнить индекс, счётчик или другую информацию — нужна Map.

Пример: Two Sum за один проход

Пусть нужно найти индексы двух элементов массива, сумма которых равна target. Для текущего числа numbers[i] можно сразу вычислить недостающее значение target - numbers[i] и проверить, встречалось ли оно раньше.

static int[] twoSum(int[] numbers, int target) {
    Map<Integer, Integer> indexByValue = new HashMap<>();

    for (int i = 0; i < numbers.length; i++) {
        int needed = target - numbers[i];
        Integer previousIndex = indexByValue.get(needed);

        if (previousIndex != null) {
            return new int[]{previousIndex, i};
        }

        indexByValue.put(numbers[i], i);
    }

    return new int[0];
}

Карта хранит значение элемента и индекс, на котором оно было встречено. Для каждого нового элемента выполняется одна ожидаемо быстрая проверка вместо просмотра всей предыдущей части массива. Поэтому ожидаемая временная сложность — O(n), а дополнительная память — O(n).

Почему сначала поиск, потом вставка

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

Как узнавать этот паттерн

• нужно быстро проверять, встречалось ли значение раньше;
• нужно найти «дополняющее» значение вместо перебора всех пар;
• нужно связать объект с уже вычисленной информацией и быстро получить её позже;
• повторный поиск по уже обработанной части делает решение квадратичным.

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