LeetCode 228. 汇总区间

Categories:

题目描述
思路分析
1. 解法一：双指针线性扫描（推荐）
相似题目

题目描述

✅ 228. 汇总区间

思路分析

解法一：双指针线性扫描（推荐）

核心思路：

维护当前区间起点 start 与上一元素 prev。

当出现断层（nums[i] != prev + 1）时，结算 [start, prev] 区间。

继续从新起点开始，最后别忘记结算尾区间。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(1)，忽略输出占用。

import java.util.*;

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 (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 nums[i] == 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)
}

相似题目

题目	难度	考察点
163. 缺失的区间	简单	区间扫描
128. 最长连续序列	中等	哈希表
56. 合并区间	中等	区间处理
57. 插入区间	中等	区间处理
989. 数组形式的整数加法	简单	数组遍历

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/71471529