Contains Duplicate II

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

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

219 Contains Duplicate IIРазбор · 1×

Пример: [7, 3, 9, 7, 4, 9, 4], k = 2. Над массивом — расстояние до прошлой копии, под ним словарь: число и его последний индекс.

07132937445964lastx: i—
ещё не дошлиуже виделитекущее числокопия слишком далекодостаточно близко

Начинаем с пустого словаря: число → последний индекс, где оно было

01/29
сначала · назад · пуск · шаг
Скорость
1function containsNearbyDuplicate(nums, k):
2 last = empty map
3 for i from 0 to len(nums) - 1:
4 x = nums[i]
5 if x in last and i - last[x] <= k:
6 return true
7 last[x] = i
8 return false
состояние
last
{}
i
–
x
–
историянажмите шаг, чтобы вернуться

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

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

  1. Важна только ближайшая прошлая копия: если хоть одна достаточно близко, то и последняя тоже. Поэтому словарь хранит для числа только последний индекс.
  2. Повтор, который слишком далеко, — ещё не ответ, но он забирает индекс себе: следующую копию числа мерим от него, а не от более старой.
  3. Сначала проверяем, потом записываем, как в Two Sum: число не мерит расстояние до самого себя.

Сложность

Время O(n): один проход, поиск в словаре O(1). Память O(n) на словарь; если хранить в множестве только последние k чисел, будет O(k).

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

Решить на LeetCode ↗

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