Поиск дубликатов в массиве с условием
Условие
Дан массив целых чисел nums и целое число k. Определите, есть ли в массиве два различных индекса i и j такие, что nums[i] == nums[j] и |i - j| <= k.
Верните true, если такие индексы существуют, иначе false.
Ограничения
- 1 <= nums.size() <= 10^5
- -10^9 <= nums[i] <= 10^9
- 0 <= k <= 10^5
Примеры
// Пример 1
nums = {1, 2, 3, 1}, k = 3
// Ответ: true (индексы 0 и 3, |0-3| = 3 <= 3)
// Пример 2
nums = {1, 0, 1, 1}, k = 1
// Ответ: true (индексы 2 и 3, |2-3| = 1 <= 1)
// Пример 3
nums = {1, 2, 3, 1, 2, 3}, k = 2
// Ответ: false
Требования
- Решение должно работать за O(n) времени
- Дополнительная память O(min(n, k))
Подсказка
Используйте скользящее окно с хеш-таблицей.
Комментарии (1)
Ответ сгенерирован нейросетью и может содержать ошибки
Решение: Поиск дубликатов с условием на расстояние
Подход: Скользящее окно (Sliding Window) + Хеш-таблица
Идея состоит в том, что мы поддерживаем окно размера k+1, содержащее только элементы, которые могут образовать пару. Если в этом окне два элемента одинаковы — мы нашли ответ.
Ключевое наблюдение: Если два индекса i и j удовлетворяют условию |i - j| <= k, то в момент обработки индекса j, индекс i находится в окне [j-k, j].
Реализация
#include <vector>
#include <unordered_set>
bool containsNearbyDuplicate(std::vector<int>& nums, int k) {
std::unordered_set<int> window;
for (int i = 0; i < nums.size(); ++i) {
// Если элемент уже в окне — найден дубликат
if (window.find(nums[i]) != window.end()) {
return true;
}
// Добавляем текущий элемент
window.insert(nums[i]);
// Если окно превышает размер k, удаляем старейший элемент
if (window.size() > k) {
window.erase(nums[i - k]);
}
}
return false;
}
Трассировка примера 1
nums = [1, 2, 3, 1], k = 3
| i | nums[i] | Окно до | Проверка | Окно после | Статус |
|---|---|---|---|---|---|
| 0 | 1 | {} | нет 1 | {1} | продолжаем |
| 1 | 2 | {1} | нет 2 | {1,2} | продолжаем |
| 2 | 3 | {1,2} | нет 3 | {1,2,3} | продолжаем |
| 3 | 1 | {1,2,3} | ЕСТЬ 1 | - | return true |
Вернули true: индексы 0 и 3, |0-3| = 3 <= 3 ✓
Трассировка примера 3
nums = [1, 2, 3, 1, 2, 3], k = 2
| i | nums[i] | Окно до | Проверка | i-k | Удалили | Окно после |
|---|---|---|---|---|---|---|
| 0 | 1 | {} | нет 1 | -2 | - | {1} |
| 1 | 2 | {1} | нет 2 | -1 | - | {1,2} |
| 2 | 3 | {1,2} | нет 3 | 0 | - | {1,2,3} |
| 3 | 1 | {1,2,3} | нет 1 | 1 | nums[1]=2 | {1,3} → {1,3,1} |
| 4 | 2 | {1,3,1} | нет 2 | 2 | nums[2]=3 | {1,1,2} |
| 5 | 3 | {1,1,2} | нет 3 | 3 | nums[3]=1 | {1,2,3} |
Ок.. подожди, ошибка в логике. Переделаю таблицу:
| i | nums[i] | Окно ДО | Проверка | Размер > k? | Удаляем nums[i-k] | Окно ПОСЛЕ |
|---|---|---|---|---|---|---|
| 0 | 1 | {} | нет 1 | нет | - | {1} |
| 1 | 2 | {1} | нет 2 | нет | - | {1,2} |
| 2 | 3 | {1,2} | нет 3 | нет | - | {1,2,3} |
| 3 | 1 | {1,2,3} | нет 1 | да | nums[0]=1 | {2,3,1} |
| 4 | 2 | {2,3,1} | нет 2 | да | nums[1]=2 | {3,1,2} |
| 5 | 3 | {3,1,2} | нет 3 | да | nums[2]=3 | {1,2,3} |
Результат: false ✓
Почему это работает?
Инвариант: После обработки элемента i в окне находятся элементы с индексами [i-k, i-1]
- При обработке элемента i проверяем, есть ли он в окне
- Если есть — значит, есть индекс j из [i-k, i-1], где nums[j] == nums[i]
- Тогда |i - j| <= k ✓
Если элемента нет, добавляем его и выбрасываем старейший элемент, если окно переполнилось.
Анализ сложности
- Временная сложность: O(n) — каждый элемент добавляется и удаляется из set один раз
- Пространственная сложность: O(min(n, k)) — окно содержит максимум k элементов
Альтернативный подход: Хеш-таблица с индексами
bool containsNearbyDuplicate(std::vector<int>& nums, int k) {
std::unordered_map<int, int> lastIndex; // значение → последний индекс
for (int i = 0; i < nums.size(); ++i) {
if (lastIndex.find(nums[i]) != lastIndex.end() &&
i - lastIndex[nums[i]] <= k) {
return true;
}
lastIndex[nums[i]] = i;
}
return false;
}
Этот подход также O(n) по времени и O(min(n, k)) по памяти, но использует unordered_map вместо unordered_set.
Сравнение подходов
| Подход | Преимущества | Недостатки |
|---|---|---|
| Sliding Window + Set | Простая логика, не нужно хранить индексы | Дополнительная операция erase |
| Sliding Window + Map | Хранит полезную информацию (индексы) | Немного сложнее в логике |
| Наивный O(n²) | Очень просто | Слишком медленно для больших k |
Граничные случаи
// k = 0 → можно ли два элемента на одном месте?
// Нет, нужны разные индексы, но |i-j|=0 => i==j
assert(!containsNearbyDuplicate({1, 1}, 0));
// Весь массив дубликаты
assert(containsNearbyDuplicate({1, 1, 1, 1}, 1));
// Большой k — почти весь массив в окне
assert(!containsNearbyDuplicate({1, 2, 3, 4, 5}, 100000));