LeetCode 228. 汇总区间

约 5 分钟
文章信息 7 个分类 1 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 面试经典 150 题 腾讯
标签
数组

题目描述

✅ 228. 汇总区间

image-20260929090848639

image-20260929090848762

题意分析

把升序且没有重复值的整数数组，表示成尽可能少的连续整数区间。每个原有数字必须恰好被覆盖一次，区间中也不能包含原数组没有的数字。

单个数字输出为 a，多个连续数字输出为 a->b。数组已经有序，不需要再排序。

解法：双指针线性扫描

核心思路

[!blue]

用 start 和 prev 保存当前尚未输出区间的起点值和终点值。读到下一个数字时，若它与 prev 相差 1，就把 prev 更新为这个数字，让当前区间继续延长。

如果相邻值之间有缺口，就必须结束当前区间：继续合并会把缺口中的数字也包含进去，违反恰好覆盖的要求。先输出 [start, prev]，再让当前数字同时成为新区间的起点和终点。

遇到连续数字就合并、遇到缺口才拆开，得到的都是不能再扩大的连续段。每个缺口都是任何合法答案都必须划分的位置，因此这些区间的数量已经最少。

判断连续时先把数值提升到 64 位再相减，避免极端端点的差值超出 32 位范围。循环只会在出现下一个缺口时输出旧区间，最后一段没有后续数字触发结算，所以循环结束后还要单独输出一次。

解题步骤

  1. 建立结果列表；空数组立即返回，避免读取不存在的首项。
  2. 用首项初始化 start 和 prev。
  3. 从第二项开始扫描，连续时只更新 prev；不连续时先格式化输出旧区间，再重置两个端点。
  4. 扫描结束后补上最后一段。
  5. 格式化时，起点等于终点就只输出该数字，否则输出 start->end。

代码实现

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

        if (nums.length == 0) {
            return res;
        }

        int start = nums[0];
        int prev = nums[0];

        for (int i = 1; i < nums.length; i++) {
            // 相邻值连续则延长当前段，否则先结算再重置。
            if ((long) nums[i] - prev == 1) {
                prev = nums[i];
                continue;
            }

            res.add(formatRange(start, prev));
            start = nums[i];
            prev = nums[i];
        }

        res.add(formatRange(start, prev));

        return res;
    }

    private String formatRange(int start, int end) {
        if (start == end) {
            return String.valueOf(start);
        }

        return start + "->" + end;
    }
}

import "strconv"

func summaryRanges(nums []int) []string {
    res := []string{}
    if len(nums) == 0 {
        return res
    }

    start := nums[0]
    prev := nums[0]

    for i := 1; i < len(nums); i++ {
        // 相邻值连续则延长当前段，否则先结算再重置。
        if int64(nums[i])-int64(prev) == 1 {
            prev = nums[i]
            continue
        }
        res = append(res, formatRange(start, prev))
        start = nums[i]
        prev = nums[i]
    }

    res = append(res, formatRange(start, prev))
    return res
}

func formatRange(start int, end int) string {
    if start == end {
        return strconv.Itoa(start)
    }
    return strconv.Itoa(start) + "->" + strconv.Itoa(end)
}

复杂度分析

  • 时间复杂度：$O(n+1)$，n 为数组长度，每个数字只处理一次；题目整数位数有固定上限，区间字符串的构造成本为常数。
  • 空间复杂度：不计输出为 $O(1)$，只保存两个端点；结果最多有 n 个区间，占 $O(n)$ 空间。

关键点总结

[!green]

  • 只在相邻数值有缺口时分段，形成的最大连续段数就是最少区间数。
  • start、prev 保存端点数值，不是数组下标。
  • 发现缺口时输出旧段，循环结束时补输出最后一段。

易错点总结

[!yellow]

  • 把有缺口的数字继续合并：会覆盖原数组中不存在的整数。
  • 漏掉循环后的输出：最后一段会丢失，整个数组连续时甚至得不到任何结果。
  • 先重置端点再输出：旧区间的起止值已经被覆盖，应先结算。
  • 空数组仍读取首项：会越界，应在初始化端点前返回。
  • 单点输出为 a->a：单点区间只应输出一个数字。

相似题目

题目 难度 关联与区别
163. 缺失的区间 简单 原题输出缺失区间，本题输出已有数形成的连续区间，边界处理互为补充。
56. 合并区间 中等 同样压缩区间表示，原题输入本身就是区间并允许重叠，本题从有序离散点构造连续段。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/71471529
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！