江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第228题：汇总区间

给定一个无重复元素的有序整数数组 nums 。 返回 恰好覆盖数组中所有数字的最小有序区间范围列表。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。 列表中的每个区间范围 [a,b] 应该按如下格式输出： - "a->b" ，如果 a != b - "a" ，如果 a == b

题目描述

给定一个无重复元素的有序整数数组 nums 。

返回 恰好覆盖数组中所有数字的最小有序区间范围列表。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出：

  • "a->b" ，如果 a != b
  • "a" ，如果 a == b

难度

简单

题目链接

点击在LeetCode中查看题目

示例

示例 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 按升序排列

解题思路

这道题要求将有序数组中的数字划分为连续的区间。解题思路非常直观：

  1. 遍历数组，寻找连续数字的起点和终点
  2. 当发现当前数字与前一个数字不连续时（相差不为1），则当前的连续区间结束
  3. 将找到的区间按要求的格式添加到结果列表中

方法：一次遍历

我们使用两个指针来记录每个区间的起始和结束位置。遍历数组，当遇到不连续的元素时（即 nums[i] != nums[i-1] + 1），就将前面的区间添加到结果列表中，并开始一个新的区间。

时间复杂度：O(n)，其中n是数组的长度，我们需要遍历数组一次。 空间复杂度：O(1)，除了返回的结果数组外，我们只需要常数级别的额外空间。

代码实现

C# 实现

public class Solution {
    public IList<string> SummaryRanges(int[] nums) {
        List<string> result = new List<string>();
        
        if (nums.Length == 0) {
            return result;
        }
        
        int start = nums[0];
        
        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] != nums[i-1] + 1) {
                // 当前数与前一个数不连续，添加区间
                if (start == nums[i-1]) {
                    result.Add(start.ToString());
                } else {
                    result.Add(start + "->" + nums[i-1]);
                }
                start = nums[i];
            }
        }
        
        // 处理最后一个区间
        if (start == nums[nums.Length - 1]) {
            result.Add(start.ToString());
        } else {
            result.Add(start + "->" + nums[nums.Length - 1]);
        }
        
        return result;
    }
}

Python 实现

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        if not nums:
            return []
        
        result = []
        start = nums[0]
        
        for i in range(1, len(nums)):
            if nums[i] != nums[i-1] + 1:
                # 当前数与前一个数不连续，添加区间
                if start == nums[i-1]:
                    result.append(str(start))
                else:
                    result.append(f"{start}->{nums[i-1]}")
                start = nums[i]
        
        # 处理最后一个区间
        if start == nums[-1]:
            result.append(str(start))
        else:
            result.append(f"{start}->{nums[-1]}")
            
        return result

C++ 实现

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> result;
        
        if (nums.empty()) {
            return result;
        }
        
        int start = nums[0];
        
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] != nums[i-1] + 1) {
                // 当前数与前一个数不连续，添加区间
                if (start == nums[i-1]) {
                    result.push_back(to_string(start));
                } else {
                    result.push_back(to_string(start) + "->" + to_string(nums[i-1]));
                }
                start = nums[i];
            }
        }
        
        // 处理最后一个区间
        if (start == nums.back()) {
            result.push_back(to_string(start));
        } else {
            result.push_back(to_string(start) + "->" + to_string(nums.back()));
        }
        
        return result;
    }
};

性能分析

各语言实现的性能对比：

实现语言 执行用时 内存消耗 说明
C# 156 ms 41.5 MB 使用列表存储结果，代码简洁
Python 36 ms 15.1 MB 使用f-string格式化字符串，效率高
C++ 0 ms 6.9 MB 性能最优，内存消耗最小

补充说明

代码亮点

  1. 使用简单的一次遍历就能解决问题，算法思路清晰
  2. 考虑了空数组的边界情况
  3. 特别处理了最后一个区间，避免遗漏

优化方向

  1. 可以在一开始就预估结果数组的大小，减少动态分配内存的开销
  2. 对于特别大的数组，可以考虑使用更高效的字符串操作方法

解题难点

  1. 正确处理区间的边界情况
  2. 理解“恰好覆盖”的含义，即需要将每个数字都划分到某个区间中

常见错误

  1. 忘记处理最后一个区间
  2. 区间格式化错误，没有按照要求的格式输出
  3. 没有考虑空数组的情况

相关题目