题目描述

给定一个从小到大排好序的数组，数组中不包含相同元素。请返回数组中的所有区间。

样例1

输入：[0,1,2,4,5,7]
输出：["0->2","4->5","7"]
解释：0,1,2 组成一个连续的区间,4,5 也组成一个连续的区间。

样例2

输入：[0,2,3,4,6,8,9]
输出：["0","2->4","6","8->9"]
解释：2,3,4 祖晨搞一个连续的区间 8,9 也组成一个连续的区间。

算法

(线性扫描) $O(n)$

从前往后扫描整个数组，扫描时维护当前区间的起点 $st$ 和终点 $ed$，如果当前数可以接在区间结尾，则更新 $ed$；否则打印 $[st, ed]$，然后将 $st$ 和 $ed$ 更新成当前数。

时间复杂度分析：每个数仅被遍历一次，所以时间复杂度是 $O(n)$。

C++ 代码

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> res;
        int st, ed;
        for (int i = 0; i < nums.size(); i ++ )
        {
            int x = nums[i];
            if (!i) st = ed = x;
            else if (x == ed + 1) ed ++ ;
            else
            {
                res.push_back(to_string(st) + (st == ed ? "" : "->" + to_string(ed)));
                st = ed = x;
            }
        }
        if (nums.size()) res.push_back(to_string(st) + (st == ed ? "" : "->" + to_string(ed)));
        return res;
    }
};