Условие

Дан массив целых чисел nums. Найдите длину самой длинной гармоничной подпоследовательности, где разница между максимальным и минимальным элементами равна 1.

Примеры

Input: nums = [1, 3, 2, 2, 5, 2, 3, 7] Output: 5 Explanation: Самая длинная гармоничная подпоследовательность — [3, 2, 2, 2, 3].

Input: nums = [1, 2, 3, 4] Output: 2 Explanation: Самая длинная гармоничная подпоследовательность — [1, 2] или [2, 3] или [3, 4].

Input: nums = [1, 1, 1, 1] Output: 0 Explanation: В массиве нет двух чисел с разницей в значении 1.

Решение

fun findLHS(nums: IntArray): Int {
    val frequencyMap = mutableMapOf<Int, Int>() // Мапа для хранения частоты каждого числа
    for (num in nums) {
        frequencyMap[num] = (frequencyMap[num] ?: 0) + 1 // Увеличиваем счетчик для текущего числа
    }

    var maxLength = 0 // Переменная для хранения максимальной длины гармоничной подпоследовательности
    for ((key, value) in frequencyMap) {
        // Проверяем, существует ли число, которое на 1 больше текущего
        if (frequencyMap.containsKey(key + 1)) {
            // Считаем длину гармоничной подпоследовательности
            val length = value + frequencyMap[key + 1]!!
            // Обновляем максимальную длину, если текущая больше
            if (length > maxLength) {
                maxLength = length
            }
        }
    }
    return maxLength
}

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

O(n), где n — длина массива.

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

O(n), для хранения карты частот.