Contains Duplicate

Лёгкая№217найти пару

Дан массив чисел. Нужно понять, есть ли в нём число, которое встречается хотя бы дважды. Наш пример: [4, 9, 1, 7, 9, 2] — да, 9 встречается два раза.

217 Contains DuplicateРазбор · 1×

Пример: [4, 9, 1, 7, 9, 2]. Под массивом — множество чисел, которые уже встретились.

041921374952seen—
ещё не дошлив множестветекущее числоповтор

Начинаем с пустого множества: ещё ни одного числа не видели

01/16
сначала · назад · пуск · шаг
Скорость
1function containsDuplicate(nums):
2 seen = empty set
3 for each x in nums:
4 if x in seen:
5 return true
6 add x to seen
7 return false
состояние
seen
{}
x
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Про число нужно знать одно: встречали ли его раньше. Множество хранит ровно это и отвечает сразу, без прохода по массиву назад.
  2. Первое же число, которое уже есть в множестве, — повтор: ответ true, остаток массива не важен.
  3. Если массив кончился без совпадений, каждое число попало в множество как новое, значит, все разные: false.

Сложность

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

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.