Easy

题目描述

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

提示：

  • 0 <= nums.length <= 20
  • -2^31 <= nums[i] <= 2^31 - 1
  • nums 中的所有值都 互不相同
  • nums 按 升序 排列

解题思路

解题思路

这是一道经典的区间合并问题。由于数组已经排序且无重复元素，我们可以使用双指针法来找出连续的数字区间。

核心思想：

  • 使用两个指针 start 和 end 来标记当前区间的开始和结束位置
  • 遍历数组，当发现相邻元素不连续时（即 nums[i] != nums[i-1] + 1），说明当前区间结束
  • 根据区间长度决定输出格式：单个数字直接输出，连续区间输出 start->end 格式

算法步骤：

  1. 处理空数组的边界情况
  2. 初始化 start 指针指向数组开头
  3. 遍历数组，寻找每个连续区间的结束位置
  4. 当发现不连续或到达数组末尾时，将当前区间加入结果
  5. 根据区间是否为单点决定输出格式

这种方法时间复杂度为 O(n)，空间复杂度为 O(1)（不考虑结果数组），是最优解法。

代码实现

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> result;
        if (nums.empty()) return result;
        
        int start = 0;
        for (int i = 0; i < nums.size(); i++) {
            // 检查是否到达区间末尾
            if (i == nums.size() - 1 || nums[i + 1] != nums[i] + 1) {
                if (start == i) {
                    // 单个数字
                    result.push_back(to_string(nums[start]));
                } else {
                    // 区间
                    result.push_back(to_string(nums[start]) + "->" + to_string(nums[i]));
                }
                start = i + 1;
            }
        }
        return result;
    }
};

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        if not nums:
            return []
        
        result = []
        start = 0
        
        for i in range(len(nums)):
            # 检查是否到达区间末尾
            if i == len(nums) - 1 or nums[i + 1] != nums[i] + 1:
                if start == i:
                    # 单个数字
                    result.append(str(nums[start]))
                else:
                    # 区间
                    result.append(f"{nums[start]}->{nums[i]}")
                start = i + 1
        
        return result

public class Solution {
    public IList<string> SummaryRanges(int[] nums) {
        var result = new List<string>();
        if (nums.Length == 0) return result;
        
        int start = 0;
        for (int i = 0; i < nums.Length; i++) {
            // 检查是否到达区间末尾
            if (i == nums.Length - 1 || nums[i + 1] != nums[i] + 1) {
                if (start == i) {
                    // 单个数字
                    result.Add(nums[start].ToString());
                } else {
                    // 区间
                    result.Add($"{nums[start]}->{nums[i]}");
                }
                start = i + 1;
            }
        }
        return result;
    }
}

var summaryRanges = function(nums) {
    if (nums.length === 0) return [];
    
    const result = [];
    let start = nums[0];
    let end = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] === end + 1) {
            end = nums[i];
        } else {
            if (start === end) {
                result.push(start.toString());
            } else {
                result.push(start + "->" + end);
            }
            start = nums[i];
            end = nums[i];
        }
    }
    
    if (start === end) {
        result.push(start.toString());
    } else {
        result.push(start + "->" + end);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组一次，每个元素访问常数次
空间复杂度O(1)除了结果数组外，只使用了常数额外空间

相关题目