Contains Duplicate II

Условие

Дан целочисленный массив nums и целое число k, верните true, если в массиве есть дубликаты, которые находятся на расстоянии не более k друг от друга. Если нет, верните false.

Примеры

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

Output: true

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

Output: true

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

Output: false

Решение

fun containsNearbyDuplicate(nums: IntArray, k: Int): Boolean {
    // Создаем мапу для хранения индексов элементов
    val indexMap = mutableMapOf<Int, Int>()
    
    // Проходим по каждому числу в массиве
    for (i in nums.indices) {
        // Если число уже встречалось и разница между текущим и предыдущим индексом меньше или равна k
        if (indexMap.containsKey(nums[i]) && i - indexMap[nums[i]]!! <= k) {
            return true // Возвращаем true
        }
        // Обновляем индекс текущего числа
        indexMap[nums[i]] = i
    }
    
    return false // Если не нашли подходящих дубликатов, возвращаем false
}

Временная сложность

O(n), где n — количество элементов в массиве, так как мы проходим по всем элементам один раз.

Пространственная сложность

O(min(n, k)), в худшем случае, если все элементы уникальны, и мы храним индексы только для k последних элементов.