Premium

Хеш-таблицы

Дубликат

Проверить содержит ли массив дубликаты

Легкий

Постановка задачи

Описание (LeetCode)

Дан целочисленный массив nums, верните true если любое значение содержится в массиве по крайней мере дважды, и верните false, если каждый элемент уникален.

Пример 1:

nums = [1, 2, 3, 1]

Результат:

true

Пояснение:

Элемент 1 содержится в массиве дважды в индексах 0 и 3.

Пример 2:

nums = [1, 2, 3, 4]

Результат:

false

Пояснение:

Все элементы уникальны в массиве.

Пример 3:

nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]

Результат:

true

Ограничения:

  • 1 <= nums.length <= 10⁵
  • -10⁹ <= nums[i] <= 10⁹

Решение

Это простая задача для разминки, которая проверяет умение работать с хеш-таблицами.

"Решение в лоб" - это интуитивный способ, который первым приходит в голову. Его логика проста: нужно проверить каждую пару чисел в массиве. Мы берем первое число и сравниваем его со всеми остальными. Затем берем второе и сравниваем с оставшимися, и так далее. Если на любом этапе мы находим два одинаковых числа - возвращаем true. Понятно, что такое решение имеет временную сложность O(n²) и не является проходным для интервью.

В реальной разработке, однако, это может использоваться (очень редко), когда вы на 100% уверены, что массив всегда будет крошечным (например, не больше 5-10 элементов), и вы не хотите выделять лишнюю память под хеш-таблицу.

Более эффективный способ решения - использовать хеш-таблицу для поддержки множества. Множество хранит только уникальные значения, а проверка наличия элемента очень быстрая.

Основные шаги:

  1. Создаем пустое множество (хеш-таблицу).
  2. Проходим по массиву:
    • Если число уже есть в множестве, мы нашли дубликат и возвращаем true.
    • Если нет, добавляем число в множество.
  3. Если цикл закончился - дубликатов нет, возвращаем false.

Оценка сложности

Временная сложность

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

Пространственная сложность

Так как мы используем хеш-таблицу, в худшем случае мы сохраним все элементы в таблице.

Таким образом пространственная сложность решения будет равна: O(n).

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

Есть другое решение, если нельзя использовать дополнительную память, - через сортировку массива. Сортируем массив и потом проходим циклом и сравниваем каждый элемент со следующим. Если они равны, мы нашли дубликат. Такое решение обычно будет O(n * log n) по времени (сортировка), но O(1) по памяти.

Код решения

Приведем код решения.

func containsDuplicate(nums []int) bool {
    seen := make(map[int]struct{})
    for _, num := range nums {
        if _, exists := seen[num]; exists {
            return true
        }
        seen[num] = struct{}{}
    }
    return false
}

Итоги

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

  1. Используйте хеш-таблицу, если важна скорость. Это "золотой стандарт" для этой задачи: работает максимально быстро O(n), жертвуя объемом оперативной памяти.

  2. Используйте сортировку, если важна память. Если вы работаете в условиях жестко ограниченной памяти, например во встроенных системах или при обработке гигантских массивов, сортировка позволяет избежать создания большой вспомогательной структуры данных.

  3. Главный урок задачи: умение переходить от полного перебора к использованию хеш-таблиц - это базовый навык, который позволяет ускорять алгоритмы с квадратичной до линейной сложности.

Войдите чтобы отмечать прогресс