Summary Ranges

Условие

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

Например, диапазон [0, 1, 2, 4, 5, 7] должен быть представлен как ["0 → 2", "4 → 5", "7"].

Примеры

Input: nums = [0, 1, 2, 4, 5, 7]

Output: ["0 → 2", "4 → 5", "7"]

Explanation: Диапазоны:

[0, 2] --> "0 → 2"
[4, 5] --> "4 → 5"
[7, 7] --> "7"

Input: nums = [0, 2, 3, 4, 6, 8, 9]

Output: ["0", "2 → 4", "6", "8 → 9"]

Explanation: Диапазоны:

[0, 0] --> "0"
[2, 4] --> "2 → 4"
[6, 6] --> "6"
[8, 9] --> "8 → 9"

Решение

fun summaryRanges(nums: IntArray): List<String> {
    val ranges = mutableListOf<String>()
    if (nums.isEmpty()) return ranges // Если массив пустой, возвращаем пустой список

    var start = nums[0] // Начальная точка диапазона

    for (i in 1 until nums.size) {
        // Проверяем, есть ли разрыв в последовательности
        if (nums[i] != nums[i - 1] + 1) {
            // Если разрыв есть, добавляем диапазон или одиночное число в список
            ranges.add(if (start == nums[i - 1]) start.toString() else "$start->${nums[i - 1]}")
            start = nums[i] // Обновляем стартовую точку
        }
    }

    // Добавляем последний диапазон или одиночное число
    ranges.add(if (start == nums.last()) start.toString() else "$start->${nums.last()}")

    return ranges
}

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

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

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

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