題目連結(https://leetcode.com/problems/summary-ranges/description)

You are given a sorted unique integer array nums.

A range [a,b] is the set of all integers from a to b (inclusive).

Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of nums is covered by exactly one of the ranges, and there is no integer x such that x is in one of the ranges but not in nums.

Each range [a,b] in the list should be output as:

• "a->b" if a != b
• "a" if a == b

限制條件

• 0 <= nums.length <= 20
• 2＾31 <= nums[i] <= 2＾31 - 1
• All the values of nums are unique.
• nums is sorted in ascending order.

寫這題需要知道字串的基本用法
想清楚兩種構成區間的情況與邊界條件

1. Repeat（題目重複確認）

• 輸入：已排序的整數陣列 nums，陣列中的元素都是唯一的。
• 輸出：一些區間，可以恰好覆蓋這些數
• 前提：nums排序是升序，且數都是唯一的，介於整數範圍。

2. Examples（舉例確認理解）

區間覆蓋範圍不能超過陣列中的數，比如說不能直接用0→4，因為沒有3。
此外，也可能出現單個數字的情況，比如說陣列最後一個數字 7 前後都沒有連續的數字。

Input: nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: The ranges are:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

3. Approach（解題思路）

方法

• 這題的重點是「時機」，要設定一個 begin 的變數，代表區間的開始索引
• 但條件不是設定前後差 1 時更新 begin，而是前後不差 1 時結束這個區間，並將索引移到下一位，表示找到新的 begin，可以開始新的區間
• 只有一個數字時，格式是 a。
• 範圍有多個數字時，格式是 a->b
• 時間複雜度：O(n)
• 空間複雜度：O(n)

4. Code（C++）

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> result;

        // 處理空陣列
        if(nums.empty()) return result;

        int begin = 0;
        for(int i = 0; i < nums.size(); i++){
            // 檢查是否到達array末位，或者當前數字與下一個數字不連續（不在同區間）
            if(i == nums.size() - 1 || nums[i+1] != nums[i] + 1){
                if(begin == i){ //只有一個數字直接加入result
                    result.push_back(to_string(nums[begin]));
                }
                else{
                    result.push_back(to_string(nums[begin]) + "->" + to_string(nums[i]));
                }
                // 更新下一個區間的開始位置
                begin = i + 1;
            }
            //如果連續的話不會進去if，i 直接加 1，begin 並不會加 1
        }
        return result;
    }
};

5. Test 範例

6. 相關題目與延伸概念

• 163. Missing Ranges
• 352. Data Stream as Disjoint Intervals
• 2655. Find Maximal Uncovered Ranges

7. 補充：語法＆注意事項

1. 溢位問題：

• 問題背景：nums[i+1] - nums[i] != 1 會有問題，因為在處理兩個數字的差時，可能會出現溢位的情況（例如 nums[i] = INT_MIN -2147483648，nums[i+1] = INT_MAX，這樣會造成溢位）。
• 解決方式：
  • 我們應該改成 nums[i+1] != nums[i] + 1，這樣可以避免溢位的問題，保證數字不會超過整數範圍。

2. 條件檢查順序：

• 條件的檢查順序很重要，如果將以下檢查的順序調換：

  if (i == nums.size() - 1 || nums[i+1] != nums[i] + 1)
  

  會在最後一個數字時出現 runtime error。因為在最後一個數字時，i+1 的位置超出了陣列範圍，會觸發訪問越界錯誤。

3. 字串相關語法

• to_string()：將整數轉為字串。
• push_back()：將元素添加到 vector 的末尾。

ps. 部分內容經 AI 協助整理