219. Contains Duplicate II

Задача

Дан массив целых чисел nums и целое число k. Верните true, если в массиве существуют два различных индекса i и j, таких что nums[i] == nums[j] и abs(i - j) <= k.

Примеры

Пример 1

Input: nums = [1,2,3,1], k = 3
Output: true

Пример 2

Input: nums = [1,0,1,1], k = 1
Output: true

Пример 3

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

Решение

Решение

// Временная сложность:  O(N) — один проход.
// Пространственная сложность:  O(N) — хеш-таблица для хранения индексов.
var containsNearbyDuplicate = function(nums, k) {
    const map = new Map(); // Значение -> Индекс
 
    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];
 
        if (map.has(num)) {
            const j = map.get(num);
            if (i - j <= k) return true;
        }
 
        map.set(num, i); // Запоминаем/Обновляем индекс
    }
 
    return false;
};
 

Решение 2

// Временная сложность:  O(N) — каждый элемент добавляется и удаляется из Set ровно 1 раз.
// Пространственная сложность: O(min(N, k)) — Set никогда не будет больше k элементов. Это лучше по памяти, если k маленькое.
 
var containsNearbyDuplicate = function(nums, k) {
    const set = new Set();
 
    for (let i = 0; i < nums.length; i++) {
        // Если число уже есть в окне — нашли дубликат!
        if (set.has(nums[i])) return true;
 
        // Добавляем текущее
        set.add(nums[i]);
 
        // Если окно переполнилось (стало больше k), выкидываем старое
        if (set.size > k) {
            set.delete(nums[i - k]);
        }
    }
 
    return false;
};