228. Summary Ranges

題目 / Problem

中文 給你一個已排序且元素皆唯一的整數陣列 nums。

一個範圍 [a,b] 表示從 a 到 b（含兩端）的所有整數。

請回傳能剛好覆蓋陣列中所有數字的最小、且已排序的範圍清單。也就是說：nums 中每個元素都被恰好一個範圍覆蓋，而且範圍裡不能出現任何「不在 nums 裡」的整數。

每個範圍 [a,b] 的輸出格式： - 若 a != b，輸出 "a->b" - 若 a == b，輸出 "a"

English 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 — every element is covered by exactly one range, and no integer outside nums appears inside any range.

Each range [a,b] is printed as: - "a->b" if a != b - "a" if a == b

Constraints / 約束 - 0 <= nums.length <= 20 - -2^31 <= nums[i] <= 2^31 - 1 - All values are unique / 所有值皆唯一 - nums is sorted ascending / nums 已升序排序

Worked example / 範例 Input: nums = [0,1,2,4,5,7] Output: ["0->2","4->5","7"] 解釋：0,1,2 連續成一段 → "0->2"；4,5 連續成一段 → "4->5"；7 自成一段 → "7"。

名詞解釋 / Glossary

• 連續區段 / Consecutive run：陣列中相鄰且差值剛好為 1 的一串數字（例如 0,1,2）。本題就是把陣列切成這些區段。 / A maximal stretch of numbers where each is exactly 1 more than the previous (e.g. 0,1,2). The whole task is splitting the array into these runs.
• 指標 / Pointer (index)：一個整數變數，用來記住「目前看到陣列的哪個位置」，例如 i、start。 / An integer variable that remembers which array position you are currently looking at, e.g. i, start.
• 不變量 / Invariant：在迴圈每一輪都保持為真的性質，幫助我們確信程式正確。本題的不變量是：start 永遠指向「當前區段的第一個元素」。 / A property that stays true on every loop iteration, giving confidence the logic is correct. Here: start always points to the first element of the current run.
• 動態陣列 / Dynamic array：大小可在執行時增長的陣列。C 用 malloc 配置記憶體；C++ 用 std::vector 自動管理。 / An array whose size can grow at runtime. In C you allocate with malloc; in C++ std::vector handles it automatically.
• malloc / free：C 的記憶體配置與釋放函式。malloc(n) 向系統要 n 個位元組並回傳指標；用完要記得釋放（本題回傳給 LeetCode，故不釋放）。 / C functions to request (malloc) and release (free) heap memory. malloc(n) returns a pointer to n bytes.
• snprintf：C 的安全字串格式化函式，把數字等內容寫進固定大小的字元緩衝區，並保證不會寫超過界線。 / A safe C function that formats values (like numbers) into a fixed-size character buffer without overflowing it.
• std::to_string：C++ 把整數轉成字串的函式，例如 to_string(42) 得到 "42"。 / A C++ function that converts an integer to its text form, e.g. to_string(42) → "42".

思路

最直覺的「暴力」想法是：把陣列裡每個數字單獨看成一段，輸出一堆單一數字。但題目要求「最小」的清單，所以連續的數字必須合併成一段，這種暴力法不符合要求。關鍵觀察是：因為陣列已經排序且唯一，連續區段就等於「相鄰兩數差恰好為 1」的一串數字。於是我們只要一次掃描陣列，用一個指標 start 記住「目前這段的起點」，然後不斷往後走，只要下一個數字仍然等於前一個加 1，就代表還在同一段裡；一旦發現「下一個數字不等於前一個加 1」或「走到陣列盡頭」，就表示當前段在此結束，我們把 nums[start] 到當前數字輸出成一個範圍，再把 start 移到下一個位置開始新的一段。輸出時只要判斷段頭和段尾是否相同：相同就印單一數字，不同就印 "頭->尾"。整個過程只掃一遍，且維持不變量「start 永遠指向當前段第一個元素」，所以正確又高效。

The brute-force idea is to emit every number as its own one-element range, but the problem demands the smallest list, so consecutive numbers must be merged — brute force fails that requirement. The key observation is that since the array is sorted and unique, a consecutive run is exactly a stretch where each neighbor differs by 1. So we do a single pass: a pointer start marks where the current run began, and we advance as long as the next value equals the previous value plus 1, meaning we are still inside the same run. The moment the next value breaks that "+1" chain (or we hit the end of the array), the current run is complete: we output the range from nums[start] to the current value, then reset start to the next position to begin a fresh run. When emitting, we compare the run's first and last element: equal → print a single number; different → print "first->last". One pass, with the invariant "start always points at the first element of the current run," makes it both correct and efficient.

逐步走查 / Walkthrough

Input / 輸入：nums = [0,1,2,4,5,7]，長度 6。 We walk i from 0 to n-1; start marks the run's beginning. 當 i 是最後一個，或 nums[i]+1 != nums[i+1] 時，就結束當前段。

最終結果 / Final result：["0->2", "4->5", "7"] ✓

Solution — C

/*
 * 演算法 / Algorithm:
 * 單次掃描，用 start 記住當前連續區段的起點。 / Single pass; `start` marks the run's start.
 * 當下一個數不等於目前數+1（或到陣列末端）時，區段結束，輸出一個範圍。
 * When the next value breaks the +1 chain (or we hit the end), close the run and emit it.
 */

// LeetCode 要求回傳一個字串陣列，並用 *returnSize 告訴呼叫端共有幾個字串。
// LeetCode wants an array of strings; *returnSize reports how many strings there are.
char** summaryRanges(int* nums, int numsSize, int* returnSize) {
    // 空陣列：沒有任何範圍，回傳數量設為 0，並回傳 NULL。
    // Empty array: zero ranges, set count to 0 and return NULL.
    if (numsSize == 0) {
        *returnSize = 0;          // 告訴呼叫端結果有 0 個 / tell caller there are 0 results
        return NULL;              // 沒有東西可回傳 / nothing to return
    }

    // 最多會有 numsSize 個範圍（每個數字各自成段時）。先配置這麼大的指標陣列。
    // At most numsSize ranges (when no two numbers are consecutive). Allocate that many string pointers.
    // sizeof(char*) 是「一個字串指標」的位元組大小。 / sizeof(char*) = size of one string pointer.
    char** result = (char**)malloc(sizeof(char*) * numsSize);

    int count = 0;                // 目前已產生的範圍數量 / how many ranges produced so far
    int start = 0;                // 當前區段的起點索引 / index where current run starts

    // 逐一檢視每個元素 / examine each element one by one
    for (int i = 0; i < numsSize; i++) {
        // 區段在此結束的條件：i 是最後一個元素，或下一個數不等於目前數 +1。
        // The run ends here if: i is the last element, OR the next value is not (current + 1).
        // 注意用 (long) 轉型避免 nums[i]+1 在 nums[i]==INT_MAX 時溢位。
        // Cast to long so nums[i]+1 won't overflow when nums[i] == INT_MAX.
        if (i == numsSize - 1 || (long)nums[i] + 1 != nums[i + 1]) {
            // 為這個範圍配置字串緩衝區。每個 int 最多 11 字元（含負號），
            // 加上 "->" 與結尾 ''，32 位元組綽綽有餘。
            // Allocate a buffer for this range. Each int needs up to 11 chars (with sign);
            // plus "->" and the terminating '', 32 bytes is plenty.
            char* buf = (char*)malloc(32);

            if (nums[start] == nums[i]) {
                // 段頭等於段尾 → 單一數字格式 "a"。
                // First equals last → single-number format "a".
                // snprintf 把數字安全地寫進 buf，最多寫 32 位元組。
                // snprintf safely writes the number into buf, at most 32 bytes.
                snprintf(buf, 32, "%d", nums[start]);
            } else {
                // 段頭不等段尾 → 範圍格式 "a->b"。
                // First differs from last → range format "a->b".
                snprintf(buf, 32, "%d->%d", nums[start], nums[i]);
            }

            result[count] = buf;  // 把這個字串存進結果陣列 / store this string in the result
            count++;              // 範圍數量加一 / one more range produced

            start = i + 1;        // 下一段從 i+1 開始 / next run starts at i+1
        }
        // 若條件不成立，代表還在同一段內，什麼都不做，繼續往後走。
        // Otherwise we are still inside the same run; do nothing and continue.
    }

    *returnSize = count;          // 回報實際範圍數量 / report the actual number of ranges
    return result;                // 回傳字串陣列 / return the array of strings
}

Solution — C++

/*
 * 演算法 / Algorithm:
 * 單次掃描，start 記住當前連續區段的起點。 / Single pass; `start` marks the run's start.
 * 當下一個數打破 +1 連續（或到末端）時，區段結束，組成一個範圍字串。
 * When the +1 chain breaks (or we reach the end), close the run and build its string.
 */
class Solution {
public:
    // 回傳 vector<string>：可自動增長的字串動態陣列。
    // Returns vector<string>: a self-growing dynamic array of strings.
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> result;            // 存放答案 / holds the answer
        int n = nums.size();              // 陣列長度 / array length
        if (n == 0) return result;        // 空陣列直接回傳空清單 / empty input → empty list

        int start = 0;                    // 當前區段起點索引 / start index of current run

        for (int i = 0; i < n; i++) {
            // 區段結束條件：i 是最後一個，或下一個數不等於目前數 +1。
            // Run ends if i is last, or next value is not (current + 1).
            // 用 long long 避免 nums[i]+1 在 INT_MAX 時溢位。
            // Use long long so nums[i]+1 won't overflow at INT_MAX.
            if (i == n - 1 || (long long)nums[i] + 1 != nums[i + 1]) {
                if (nums[start] == nums[i]) {
                    // 單一數字 → 直接用 to_string 把整數轉成字串並加入結果。
                    // Single number → to_string converts the int to text; push it.
                    result.push_back(to_string(nums[start]));
                } else {
                    // 範圍 "a->b" → 用 + 串接字串。to_string 處理數字轉文字。
                    // Range "a->b" → concatenate with +. to_string handles int-to-text.
                    result.push_back(to_string(nums[start]) + "->" + to_string(nums[i]));
                }
                start = i + 1;            // 下一段從 i+1 開始 / next run starts at i+1
            }
            // 否則仍在同一段內，繼續。 / Otherwise still in the same run; continue.
        }

        return result;                    // 回傳所有範圍 / return all ranges
    }
};

複雜度 / Complexity

• Time: O(n) — 我們只把陣列從頭到尾掃一遍，每個元素做常數次比較與（最多一次）字串組裝。n 是 nums 的長度。 / We scan the array once; each element does a constant amount of comparison and at most one string build. n is the length of nums.
• Space: O(1) 額外空間（不含輸出）— 只用了 start、i、count 等少數變數；輸出本身需要 O(n) 但那是必要的回傳結果。 / O(1) extra space beyond the output — only a few scalar variables. The output itself is O(n), but that is the required result, not auxiliary scratch space.

Pitfalls & Edge Cases

• 整數溢位 / Integer overflow：當 nums[i] == INT_MAX (2^31-1) 時，nums[i] + 1 會溢位成負數，導致比較錯誤。程式用 (long) / (long long) 轉型把加法放大到更寬的型別來避免。 / When nums[i] is INT_MAX, nums[i]+1 overflows to a negative number and breaks the comparison; casting to a wider type fixes it.
• 空陣列 / Empty input：nums.length == 0 時必須回傳空清單，C 版還要把 *returnSize 設成 0，否則呼叫端會讀到垃圾值。 / With an empty array, return an empty list; the C version must also set *returnSize = 0, or the caller reads garbage.
• 單一元素段 / Single-element run：要正確判斷段頭等於段尾（nums[start] == nums[i]）以輸出 "a" 而非 "a->a"。 / Must compare first vs. last so a length-1 run prints "a", not "a->a".
• 末端區段 / Last run：最後一段沒有「下一個元素」可比較，務必用 i == n-1 這個條件把它收尾，否則最後一段會漏輸出。 / The final run has no "next" element; the i == n-1 check closes it, otherwise the last range is dropped.
• C 的記憶體 / C memory sizing：字串緩衝區要夠大。一個 32 位元整數最多 -2147483648（11 字元），"a->b" 加結尾 '\0' 需要約 24 字元，配置 32 是安全的。 / The buffer must be big enough: a 32-bit int is up to 11 chars, and "a->b" plus '\0' fits comfortably in 32 bytes.
• 回傳數量 / returnSize confusion：C 版用 count（實際段數）而非 numsSize 設定 *returnSize，因為合併後範圍數通常少於元素數。 / Set *returnSize from count (actual ranges), not numsSize, since merging usually yields fewer ranges than elements.