题目描述（中等难度）

给一个数组，把连续的数字写成 的形式。

解法一

直接按照题目意思遍历一遍就可以。判断是否连续只需要判断当前数字和后一个数字是否相差 1 即可。发生不连续的时候，将当前范围保存起来。

解法二

上边解法不管最好还是最坏，时间复杂度都是 O(n)，分享 ) 的一个解法，可以对某些情况进行优化。

这里带来一个问题，判断右半部分的时候，我们知道 4 -> 5，但是它应该和左半部连接起来变成 1 -> 5。这里的话，我们需要定义一个 Range 类，当加入新的范围的时候，判断一下两个范围是否相连即可。

class Range {
    int start;
    int end;
    Range(int s, int e) {
        start = s;
        end = e;
    }
}
public List<String> summaryRanges(int[] nums) {
    List<String> resStr = new ArrayList<>();
        return resStr;
    }
    List<Range> res = new ArrayList<>();
    helper(nums, 0, nums.length - 1, res);
    for (Range r : res) {
        if (r.start == r.end) {
            resStr.add(Integer.toString(r.start));
        } else {
            resStr.add(r.start + "->" + r.end);
        }
    }
    return resStr;
}
    if (i == j || nums[j] - nums[i] == j - i) {
        add2res(nums[i], nums[j], res);
        return;
    }
    int m = (i + j) / 2;
    //一半一半的考虑
    helper(nums, i, m, res);
    helper(nums, m + 1, j, res);
}
private void add2res(int a, int b, List<Range> res) {
    //判断新加入的范围和之前最后一个范围是否相连
    if (res.isEmpty() || res.get(res.size() - 1).end + 1 != a) {
        res.add(new Range(a, b));
    } else {
        res.get(res.size() - 1).end = b;
}

虽然最坏的时间复杂度依旧是 O(n)（比如所有的数字全部不相连），但对于某些情况带来了很大的提升。

总

解法一就是根据题意写出的一个解法，解法二的话通过二分的方式对解法带来了一定程度上的优化。

添加好友一起进步~

如果觉得有帮助的话，可以点击 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情