Условие

Дан непустой массив неотрицательных целых чисел nums. Степень массива определяется как максимальная частота любого из его элементов.

Ваша задача – найти минимально возможную длину (непрерывного) подмассива nums, который имеет ту же степень, что и массив nums.

Примеры

Input: nums = [1, 2, 2, 3, 1] Output: 2 Explanation: Степень массива равна 2 (элементы 1 и 2). Короткий подмассив: [2,2].

Input: nums = [1, 2, 2, 3, 1, 4, 2] Output: 6 Explanation: Степень массива равна 3 (элемент 2). Короткий подмассив: [2,2,3,1,4,2].

Решение

fun findShortestSubarray(nums: IntArray): Int {
    val left = mutableMapOf<Int, Int>() // Хранит первую позицию элемента
    val right = mutableMapOf<Int, Int>() // Хранит последнюю позицию элемента
    val count = mutableMapOf<Int, Int>() // Хранит частоту элементов

    for (i in nums.indices) {
        val num = nums[i]
        if (num !in left) left[num] = i // Первая встреча элемента
        right[num] = i // Последняя встреча элемента
        count[num] = count.getOrDefault(num, 0) + 1 // Увеличиваем частоту
    }

    val degree = count.values.maxOrNull() ?: 0 // Находим степень массива
    var minLength = Int.MAX_VALUE

    for ((num, freq) in count) {
        if (freq == degree) {
            val length = right[num]!! - left[num]!! + 1 // Длина подмассива
            minLength = minOf(minLength, length)
        }
    }
    return minLength
}

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

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

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

O(n), так как используются дополнительные структуры для хранения позиций и частот.