題目

給定一個 無重復(fù)元素 的 有序 整數(shù)數(shù)組 nums。

返回 恰好覆蓋數(shù)組中所有數(shù)字 的 最小有序 區(qū)間范圍列表。也就是說，nums 的每個元素都恰好被某個區(qū)間范圍所覆蓋，并且不存在屬于某個范圍但不屬于 nums 的數(shù)字 x。

列表中的每個區(qū)間范圍 [a,b] 應(yīng)該按如下格式輸出：

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

示例 1：

• 輸入：nums = [0,1,2,4,5,7]
• 輸出：["0->2","4->5","7"]
• 解釋：區(qū)間范圍是：
  [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"]
• 解釋：區(qū)間范圍是：
  [0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"

方法一：一次遍歷

思路及解法

我們從數(shù)組的位置 0 出發(fā)，向右遍歷。每次遇到相鄰元素之間的差值大于 11 時，我們就找到了一個區(qū)間。遍歷完數(shù)組之后，就能得到一系列的區(qū)間的列表。

在遍歷過程中，維護(hù)下標(biāo) 和 分別記錄區(qū)間的起點和終點，對于任何區(qū)間都有 。當(dāng)?shù)玫揭粋€區(qū)間時，根據(jù) 和 的值生成區(qū)間的字符串表示。

• 當(dāng) 時，區(qū)間的字符串表示為 ‘‘"；

• 當(dāng) 時，區(qū)間的字符串表示為 ‘‘"。

代碼

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
    }
}

復(fù)雜度分析

• 時間復(fù)雜度：時間復(fù)雜度：，其中 為數(shù)組的長度。

• 空間復(fù)雜度：空間復(fù)雜度：。除了用于輸出的空間外，額外使用的空間為常數(shù)。