题目描述

给定一个无重复元素的有序整数数组，返回数组区间范围的汇总。

样例

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

输入: [0,2,3,4,6,8,9]
输出: ["0","2->4","6","8->9"]
解释: 2,3,4 可组成一个连续的区间; 8,9 可组成一个连续的区间。

算法分析

双指针

• i是连续区间的起点，j往后走一直找连续区间的终点，[i,j - 1]指针维护的是当前连续的区间，

时间复杂度 $O(n)$

Java 代码

class Solution {
    public List<String> summaryRanges(int[] nums) {
        int n = nums.length;
        List<String> ans = new ArrayList<String>();
        for(int i = 0;i < n;i ++)
        {
            int j = i + 1;
            while(j < n && nums[j] == nums[j - 1] + 1) j ++;
            int a = nums[i], b = nums[j - 1];
            if(i == j - 1) ans.add("" + a);
            else ans.add(a + "->" + b);
            i = j - 1;
        }
        return ans;
    }
}