汇总区间 图解题解

这道题到底在问什么

输入

nums=[0,1,2,4,5,7]

输出

["0->2","4->5","7"]

输入

nums=[1,3,5]

输出

["1","3","5"]（都不连续）

最优解：一步一步想明白

1. 3记住「看下一个是不是 +1：是就延伸，不是就收尾」，下面每帧都在套它。
2. 4扫到 0（紫色），绿色是当前正在生长的区间。看它的下一个 1 是不是正好等于 0+1=1？
3. 51 正好是 0+1，连续！绿色区间往右长一格，包进 1，起点仍是 0。继续往后看。
4. 6扫到 1（紫色），绿色是当前正在生长的区间。看它的下一个 2 是不是正好等于 1+1=2？
5. 72 正好是 1+1，连续！绿色区间往右长一格，包进 2，起点仍是 0。继续往后看。
6. 8扫到 2（紫色），绿色是当前正在生长的区间。看它的下一个 4 是不是正好等于 2+1=3？
7. 94 不等于 2+1，断开。这段从 0 连到 2，输出 "0->2"。这段变蓝表示已汇总，下一个数另起一段。
8. 10扫到 4（紫色），绿色是当前正在生长的区间。看它的下一个 5 是不是正好等于 4+1=5？
9. 115 正好是 4+1，连续！绿色区间往右长一格，包进 5，起点仍是 4。继续往后看。
10. 12扫到 5（紫色），绿色是当前正在生长的区间。看它的下一个 7 是不是正好等于 5+1=6？
11. 137 不等于 5+1，断开。这段从 4 连到 5，输出 "4->5"。这段变蓝表示已汇总，下一个数另起一段。
12. 14扫到 7（紫色），绿色是当前正在生长的区间。看它的下一个 8 是不是正好等于 7+1=8？
13. 158 正好是 7+1，连续！绿色区间往右长一格，包进 8，起点仍是 7。继续往后看。
14. 16扫到 8（紫色），绿色是当前正在生长的区间。看它的下一个 9 是不是正好等于 8+1=9？
15. 179 正好是 8+1，连续！绿色区间往右长一格，包进 9，起点仍是 7。继续往后看。
16. 18扫到 9（紫色），绿色是当前正在生长的区间。看它的下一个 11 是不是正好等于 9+1=10？
17. 1911 不等于 9+1，断开。这段从 7 连到 9，输出 "7->9"。这段变蓝表示已汇总，下一个数另起一段。
18. 20扫到 11（紫色），绿色是当前正在生长的区间。看它的下一个 13 是不是正好等于 11+1=12？
19. 2113 不等于 11+1，断开。这段只有 11 一个数，落单，输出 "11"。这段变蓝表示已汇总，下一个数另起一段。
20. 22扫到最后一个 13（紫色）。后面没有数了，当前这段绿色区间必须收尾。
21. 23到末尾。这段只有 13 一个数，落单，输出 "13"。这段变蓝表示已汇总，下一个数另起一段。
22. 24扫完全程，整个数组被切成 5 段连续区间：0->2、4->5、7->9、11、13。一遍扫描、不回头，就把所有区间汇总好了。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        ans = []
        i = 0
        while i < len(nums):
            start = nums[i]
            while i + 1 < len(nums) and nums[i + 1] == nums[i] + 1:
                i += 1
            if start == nums[i]:
                ans.append(str(start))
            else:
                ans.append(f"{start}->{nums[i]}")
            i += 1
        return ans

#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> ans;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            int start = nums[i];
            while (i + 1 < n && nums[i + 1] == nums[i] + 1) ++i;
            if (start == nums[i]) ans.push_back(to_string(start));
            else ans.push_back(to_string(start) + "->" + to_string(nums[i]));
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> ans = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int start = nums[i];
            while (i + 1 < nums.length && nums[i + 1] == nums[i] + 1) i++;
            if (start == nums[i]) ans.add(String.valueOf(start));
            else ans.add(start + "->" + nums[i]);
        }
        return ans;
    }
}

复杂度

面试官可能追问