Leetcode-228-汇总区间

题目描述

• 给定一个无重复元素的有序整数数组 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 出发，向右遍历。
• 每次遇到相邻元素之间的差值大于 1 时，我们就找到了一个区间。遍历完数组之后，就能得到一系列的区间的列表。
• 在遍历过程中，维护下标 low 和 high 分别记录区间的起点和终点
  • 对于任何区间都有 low <= high
  • 当得到一个区间的时候，根据low 和 high 的值生成区间的字符串表示
    • low <= high ，区间的字符串表示为“nums[low] ->nums[high]”
    • low == high ，区间的字符串表表示为"nums[low]"

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> res = new ArrayList<String>();                               // 结果集

        // 1. 遍历数组
        int idx = 0;
        int n = nums.length;
        while(idx < n){
            // 1.1 区间扩大 ： 区间未断开
            int low = idx;                                                      // 记录区间的起
            idx++;                                                              // ++到下一个位置 
            while(idx < n && nums[idx] == nums[idx - 1] + 1){                   // 如果区间没有断开
                idx++;                                                          // 将区间进行扩大
            }
            // 1.2 记录区间的终点 ： 断开退出循环
            int high = idx - 1;                                                 // 记录区间的终点
            // 1.3 处理结果
            StringBuilder temp = new StringBuilder(Integer.toString(nums[low]));// 首先加入起点位置,如果low < high，当前区间为nums[low]]本身
            if(low < high){                                                     // low < high 说明是一个完整连续的区间
                temp.append("->");
                temp.append(Integer.toString(nums[high]));                      // low -> high
            }                   
            // 1.4 加入到结果集中
            res.add(temp.toString());
        }
        return res;
    }
}

复杂度分析

• 时间复杂度 ： O(n) 其中n 为数组的长度
• 空间复杂度 ： O(1) 没有使用额外的空间

打赏