【力扣简单】228 - 汇总区间

雨点打透心脏的1/2处 2023-01-04 13:21 175阅读 0赞

![20210110103457542.jpg][]

## 一、题目描述： ##

给定一个无重复元素的有序整数数组 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”

示例 3：

> 输入：nums = \[\]  
> 输出：\[\]

示例 4：

> 输入：nums = \[-1\]  
> 输出：\["-1"\]

示例 5：

> 输入：nums = \[0\]  
> 输出：\[“0”\]

### 提示： ###

> 0 <= nums.length <= 20  
> \-231 <= nums\[i\] <= 231 - 1  
> nums 中的所有值都 互不相同  
> nums 按升序排列

## 二、解答 ##

### 分析 ###

解题思路：

1.  遍历整个数组，当相邻的数只相差1时，构成一个区间。
2.  当相邻的数相差大于1时，开始一个新的区间。
3.  当判断开始一个新的区间时，我们需要保存前面的区间。
4.  保存一个区间需要两个值分别记录区间开始的值，当前数的前一个数的值。
5.  唯一值得注意的是处理边界问题。

> 时间复杂度：O(n)，其中 n 为数组的长度。我们只需要遍历一次数组即可。  
> 空间复杂度：O(1)。只需要常数空间存放若干变量。

### 代码 ###

class Solution { 
        public List<String> summaryRanges(int[] nums) { 
            int length = nums.length;
            List<String> result = new ArrayList<>();
            if(length == 0){ 
                return result;
            }
            int start = nums[0];
            int now = nums[0];
            int  i = 1;
            for(;i < length;i++){ 
                if(now + 1 == nums[i]){ 
                    now++;
                } else{ 
                    result.add(start == now?String.valueOf(start):start+"->"+now);
                    start = now = nums[i];
                }
            }
            result.add(start == now?String.valueOf(start):start+"->"+now);
            return result;
        }
    }

> 执行用时：7 ms, 在所有 Java 提交中击败了82.54%的用户  
> 内存消耗：36.9 MB, 在所有 Java 提交中击败了53.76%的用户

### 改进 ###

1.  因为当前数的前一个数的值，我可以通过当前的下标来获取，所以该值完全没有必要记录，所以可以省略该值
2.  省略该值之后，我只要通过下标来判断即可，所以在循环里，我只要判断前一个数加一与当前值不相等即可

public List<String> summaryRanges(int[] nums) { 
            int length = nums.length;
            List<String> result = new ArrayList<>();
            if(length == 0){ 
                return result;
            }
            int start = nums[0];
            int  i = 1;
            for(;i < length;i++){ 
                if(nums[i - 1] + 1 != nums[i]){ 
                    result.add(start == nums[i - 1]?String.valueOf(start):start+"->"+nums[i - 1]);
                    start = nums[i];
                }
            }
            result.add(start == nums[i - 1]?String.valueOf(start):start+"->"+nums[i - 1]);
            return result;
        }

这样做的好处就是节省了一定的空间。

## 三、官方解答 ##

官方给出的题解也是一次遍历，但是是用双指针的方法，也就是使用维护下标low 和 high 分别记录区间的起点和终点，和我的大致思想也差不多。

class Solution { 
        public List<String> summaryRanges(int[] nums) { 
            List<String> ret = new ArrayList<String>();
            int i = 0;
            int n = nums.length;
            while (i < n) { 
                int low = i;
                i++;
                while (i < n && nums[i] == nums[i - 1] + 1) { 
                    i++;
                }
                int high = i - 1;
                StringBuffer temp = new StringBuffer(Integer.toString(nums[low]));
                if (low < high) { 
                    temp.append("->");
                    temp.append(Integer.toString(nums[high]));
                }
                ret.add(temp.toString());
            }
            return ret;
        }
    }

> 参考：  
> 1、[题目][Link 1]  
> 2、[官方解答][Link 2]

> 本文首发于CSDN，作者：lomtom  
> 原文链接：**[https://blog.csdn.net/lomtom/article/details/112306554][https_blog.csdn.net_lomtom_article_details_112306554]**  
> 个人网站：**[https://lomtom.top][https_lomtom.top]**，公众号：**博思奥园**，同步更新。  
> 你的支持就是我最大的动力。

![20200405094243147.png][]

[20210110103457542.jpg]: /images/20221119/a4226c86d40d40f1996a3bd955a3590b.png
[Link 1]: https://leetcode-cn.com/problems/summary-ranges/
[Link 2]: https://leetcode-cn.com/problems/summary-ranges/solution/hui-zong-qu-jian-by-leetcode-solution-6zrs/
[https_blog.csdn.net_lomtom_article_details_112306554]: https://blog.csdn.net/lomtom/article/details/112306554
[https_lomtom.top]: https://lomtom.top
[20200405094243147.png]: /images/20221119/9e140c6e867141dcbd27eb54de9507d7.png