От полного перебора к узкому месту

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

Когда задача просит найти дубликат

Дан массив целых чисел. Нужно ответить, есть ли в нём два одинаковых значения. Требуются разные индексы: один элемент нельзя использовать как «дубликат самого себя».

Как выглядит честный перебор пар

Для каждого индекса i можно проверить все индексы j > i. Такой алгоритм действительно рассматривает каждую пару разных позиций и поэтому корректен. В худшем случае, когда дубликатов нет, он выполнит n(n - 1) / 2 сравнений.

Где повторяется поиск

Когда мы переходим к новому элементу, снова просматривается почти весь уже проверенный префикс. Вопрос «встречалось ли значение раньше?» задаётся много раз, а ответ каждый раз ищется линейно. Именно этот повторный поиск превращает решение в O(n²).

Что достаточно помнить о префиксе

Нам не нужны сами пары и не нужен их порядок. Достаточно после каждого шага помнить множество значений из обработанного префикса. Тогда проверка текущего значения отвечает на нужный вопрос напрямую.

Что именно содержит seen

Перед обработкой values[i] множество seen содержит ровно значения с индексов от 0 до i - 1. Поэтому наличие values[i] в seen означает существование более раннего равного элемента и гарантирует разные индексы.

Проход от проверки к вставке

1. Создать пустое множество seen.
2. Идти по массиву слева направо.
3. Если текущее значение уже есть в seen, вернуть true.
4. Иначе добавить значение в seen и продолжить.
5. Если проход завершился, вернуть false.

Порядок шагов 3 и 4 важен для ясного инварианта: сначала проверяем только прошлые позиции, затем расширяем префикс.

Линейное решение с множеством

C++17

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

using namespace std;

bool hasDuplicate(const vector<int>& values) {
    unordered_set<int> seen;

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

    return false;
}

int main() {
    assert(hasDuplicate({1, 2, 1}));
    assert(!hasDuplicate({1, 2, 3}));
    assert(!hasDuplicate({}));
    assert(hasDuplicate({-4, -4}));
}

Python 3

def has_duplicate(values: list[int]) -> bool:
    seen: set[int] = set()

    for value in values:
        if value in seen:
            return True
        seen.add(value)

    return False


assert has_duplicate([1, 2, 1])
assert not has_duplicate([1, 2, 3])
assert not has_duplicate([])
assert has_duplicate([-4, -4])

Средняя цена хеширования

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

Какие дубликаты проверяют границы

• Пустой массив и один элемент не содержат пары.
• Дубликат может находиться рядом или на разных концах.
• Отрицательные числа и ноль ничем не отличаются от положительных ключей.
• Много повторов одного значения: алгоритм завершится на втором вхождении.
• Если элементы нельзя хешировать, понадобится другое представление или сортировка.

Набор тестов для разных позиций

Минимальный набор: [] → false, [7] → false, [1, 2, 1] → true, [1, 2, 3] → false, [-4, -4] → true. Случай без дубликатов важен: он заставляет выполнить весь проход.

Сигнал «видели ли раньше?»

Ищи такую оптимизацию, когда полный перебор многократно задаёт вопрос «видели ли мы раньше этот ключ?», а порядок прошлых элементов не важен. Частые формулировки: дубликат, повтор, принадлежность, уже встреченное значение.

Когда сортировка или перебор уместнее

Множество не подходит, если нужен точный порядок элементов, все пары дубликатов или строгая гарантия худшего времени без допущений о хешировании. При очень маленьком n простой перебор пар может быть понятнее и экономить память.

Почему проверяем до вставки

Вопрос. Почему проверка выполняется до вставки текущего значения?

Ответ. Тогда seen содержит только более ранние позиции. Если сначала вставить значение, проверка всегда найдёт хотя бы только что добавленный элемент и ошибочно разрешит использовать один индекс дважды.

Чем отличается решение сортировкой

Вопрос. Почему сортировка тоже может решить задачу и чем она отличается?

Ответ. После сортировки равные значения стоят рядом, поэтому достаточно проверить соседей за O(n log n) времени. Сортировка может изменить порядок входа, зато при сортировке на месте требует меньше дополнительной памяти, чем множество.

Возвращаем первое повторившееся значение

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

От перебора к точному состоянию

Корректный перебор назвал кандидатов, анализ нашёл повторный поиск в префиксе, а множество сохранило ровно ту информацию, которая превращает этот поиск в ожидаемое O(1).