题目

给定一个 无重复元素 的 有序 整数数组 nums。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x。

列表中的每个区间范围 [a,b] 应该按如下格式输出：

• "a->b"，如果 a != b
• "a"，如果 a == b

示例 1：

• 输入：nums = [0,1,2,4,5,7]
• 输出：["0->2","4->5","7"]
• 解释：区间范围是：
  [0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

示例 2：

• 输入：nums = [0,2,3,4,6,8,9]
• 输出：["0","2->4","6","8->9"]
• 解释：区间范围是：
  [0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"

方法一：一次遍历

思路及解法

我们从数组的位置 0 出发，向右遍历。每次遇到相邻元素之间的差值大于 11 时，我们就找到了一个区间。遍历完数组之后，就能得到一系列的区间的列表。

在遍历过程中，维护下标 和 分别记录区间的起点和终点，对于任何区间都有 。当得到一个区间时，根据 和 的值生成区间的字符串表示。

• 当 时，区间的字符串表示为 ‘‘"；

• 当 时，区间的字符串表示为 ‘‘"。

代码

class Solution {
    func summaryRanges(_ nums: [Int]) -> [String] {
        var ret: [String] = []
        var i = 0
        while i < nums.count {
            let low = i
            i += 1
            while i < nums.count && nums[i] == (nums[i - 1] + 1) {
                i += 1
            }
            let high = i - 1
            var tem: String = String(nums[low])
            if high > low {
                tem += "->"
                tem += String(nums[high])
            }
            ret.append(tem)
        }
        return ret
    }
}

复杂度分析

• 时间复杂度：时间复杂度：，其中 为数组的长度。

• 空间复杂度：空间复杂度：。除了用于输出的空间外，额外使用的空间为常数。