Contains Duplicate II (Дубликаты на расстоянии)
Описание: Определите, есть ли в массиве два одинаковых элемента, индексы которых отличаются не более чем на k.
Пример 1:
Вход: nums = [1,2,3,1], k = 3
Выход: true
Объяснение: Единицы стоят на индексах 0 и 3, разница ровно 3
Пример 2:
Вход: nums = [1,2,3,1,2,3], k = 2
Выход: false
Объяснение: Ближайшие одинаковые отстоят на 3
Ограничения:
1 <= nums.length <= 10⁵
0 <= k <= 10⁵
Рекомендуемая временная и пространственная сложность
Стремитесь к O(n) по времени.
Подсказка 1
Проверка всех пар даёт O(n²). Что если запоминать, где элемент встречался?
Подсказка 2
Храните в словаре последнюю позицию каждого значения.
Подсказка 3
Встретили значение снова — сравните разность индексов с k и обновите позицию.