3731. Find Missing Elements

題目 / Problem

中文： 給你一個由唯一整數組成的陣列 nums（沒有重複值）。原本這個陣列包含某個範圍內的每一個整數，但有些整數可能不見了。範圍的最小值和最大值一定還在陣列裡。請回傳這個範圍內所有缺失整數的排序清單；若沒有缺失，回傳空清單。

English: You are given an array nums of unique integers. Originally it contained every integer in some range, but some may have gone missing. The smallest and largest values of the range are still present. Return a sorted list of all missing integers in the range [min, max], or an empty list if none are missing.

Constraints / 限制： - 2 <= nums.length <= 100 - 1 <= nums[i] <= 100 - 所有元素互不相同 / all elements are distinct.

Worked example / 範例： nums = [1,4,2,5] → min = 1, max = 5，完整範圍是 [1,2,3,4,5]，只有 3 不見了，所以輸出 [3]。

名詞解釋 / Glossary

• 範圍 min/max / range min & max：陣列中的最小值與最大值。因為題目保證兩端點都在，所以完整範圍就是 [min, max]。 / The smallest and largest values; the full range is guaranteed to span exactly from min to max.
• 雜湊表 / hash table (lookup set)：一種能以 O(1) 平均時間判斷「某個值是否存在」的資料結構。這裡我們用一個布林陣列 seen[] 當作最簡單的雜湊表：seen[v] == true 表示 v 出現過。 / A structure for O(1) "is this value present?" checks. We use a boolean array seen[] as the simplest form: seen[v] == true means v appeared.
• 標記陣列 / marker (frequency) array：因為數值範圍很小（1–100），我們可以開一個以「數值本身」當索引的陣列，直接用索引標記存在與否，比一般雜湊表更快更簡單。 / Since values are tiny (1–100), we index an array by the value itself and mark presence — faster and simpler than a general hash map.
• malloc / 動態記憶體配置：在 C 裡向系統要一塊記憶體來存放回傳陣列。LeetCode 要求回傳的陣列必須是動態配置的（不能是區域變數），否則函式結束後記憶體會失效。 / In C, request memory from the system for the result array; LeetCode requires the returned array to be heap-allocated (a local array would be destroyed on return).
• 回傳大小指標 / return-count pointer (returnSize)：LeetCode 的 C 函式用一個 int* 參數把「回傳陣列的長度」傳回給呼叫者。你必須把長度寫進 *returnSize。 / An int* out-parameter used to report the result length back to the caller; you write the length into *returnSize.

思路

最直接的暴力想法是：對於範圍 [min, max] 中的每一個整數，都去掃一遍整個 nums 陣列看它在不在。這是可行的，但每次查找都要走一遍陣列，若範圍大小是 R、陣列長度是 n，總共要 O(R·n) 次比較，稍嫌浪費。我們可以用「空間換時間」：先找出 min 和 max，再開一個標記陣列 seen[]，把 nums 裡出現過的每個值都標記為「存在」。因為題目保證數值介於 1 到 100，這個標記陣列非常小。接著只要從 min 走到 max，凡是 seen[v] 為假（也就是沒被標記到）的值，就是缺失的整數，依序收集起來。由於我們是從小到大遍歷，收集到的結果天生就是排序好的，不需要額外排序。這個標記陣列本質上就是最簡單的雜湊表：用值當索引，O(1) 就能判斷存在與否。

The brute-force idea is: for each integer in [min, max], scan the whole array to check membership — correct, but O(R·n) comparisons where R is the range size and n the array length. We trade space for time instead. First find min and max, then build a marker array seen[] and flag every value that appears in nums. Because values are bounded by 1–100, this array is tiny. Then walk from min up to max; any value whose seen flag is false was never in the array, so it is missing. Since we iterate in increasing order, the collected result is already sorted — no extra sort needed. That marker array is essentially the simplest possible hash table: index by the value itself for O(1) presence checks.

逐步走查 / Walkthrough

輸入 / Input: nums = [1,4,2,5]

Step 1 — 找 min/max / find min & max: 掃描一遍，得到 min = 1, max = 5。

Step 2 — 建立標記陣列 / build seen[]: 把每個值標記為存在。

Step 3 — 從 min 走到 max 收集缺失 / sweep [min, max]:

Output: [3] ✅

Solution — C

// 演算法 / Algorithm:
// 1) 掃一遍找出 min 與 max。 / Scan once to find min and max.
// 2) 用布林陣列 seen[] 標記每個出現過的值（值域小，1..100）。 / Mark presence in seen[].
// 3) 從 min 到 max 逐一檢查，未標記者即為缺失，依序收集（天生排序）。 / Collect unmarked = sorted missing.

/**
 * 注意 / Note: 回傳的陣列必須用 malloc 動態配置，
 * 並把長度寫進 *returnSize。 / Result must be heap-allocated; write length to *returnSize.
 */
int* findMissing(int* nums, int numsSize, int* returnSize) {
    // seen[v] 表示值 v 是否出現過；索引 0..100，故大小 101。
    // seen[v] tells whether value v appeared; indices 0..100, so size 101.
    // 用 {0} 把整個陣列初始化為 0（false）。/ {0} zero-initializes the whole array (all false).
    int seen[101] = {0};

    // 先用第一個元素當作 min 與 max 的初始值。/ Seed min & max with the first element.
    int minVal = nums[0];
    int maxVal = nums[0];

    // 走一遍陣列：更新 min/max，並標記存在。/ One pass: update min/max and mark presence.
    for (int i = 0; i < numsSize; i++) {
        int v = nums[i];                  // 取出目前的值 / current value
        if (v < minVal) minVal = v;       // 更小就更新 min / shrink min
        if (v > maxVal) maxVal = v;       // 更大就更新 max / grow max
        seen[v] = 1;                      // 標記 v 存在（1 = true）/ mark v as present
    }

    // 範圍內最多可能缺 (maxVal - minVal + 1) 個數，配置這麼大足夠。
    // At most (maxVal - minVal + 1) values in range; allocate that many to be safe.
    int capacity = maxVal - minVal + 1;
    // malloc 向系統要記憶體；sizeof(int) 是一個 int 的位元組數。
    // malloc requests memory; sizeof(int) is the byte size of one int.
    int* result = (int*)malloc(sizeof(int) * capacity);

    int k = 0;  // k 是下一個寫入位置，也等於已找到的缺失數量 / k = next write slot = count so far

    // 從 min 到 max 逐一檢查（含兩端）。/ Sweep every value in [min, max], inclusive.
    for (int v = minVal; v <= maxVal; v++) {
        // seen[v] 為 0（false）代表 v 沒出現，就是缺失的。
        // seen[v] == 0 means v never appeared, i.e. it is missing.
        if (seen[v] == 0) {
            result[k] = v;  // 把缺失值寫進結果陣列 / store the missing value
            k++;            // 位置往後移一格 / advance write slot
        }
    }

    *returnSize = k;  // 透過指標回傳結果長度給呼叫者 / report length via the out-pointer
    return result;    // 回傳動態配置的結果陣列 / return the heap-allocated array
}

Solution — C++

// 演算法 / Algorithm:
// 1) 用 minmax 找出範圍兩端。 / Find range endpoints with min/max.
// 2) 用 vector<bool> seen 標記出現過的值（值域 1..100）。 / Mark presence in a boolean vector.
// 3) 從 min 到 max 收集未出現的值，順序遍歷所以結果已排序。 / Collect in order → already sorted.

class Solution {
public:
    vector<int> findMissing(vector<int>& nums) {
        // vector<bool> 是一個布林陣列；大小 101 可容納索引 0..100。
        // vector<bool> is a boolean array; size 101 covers indices 0..100.
        vector<bool> seen(101, false);

        // *min_element / *max_element 回傳範圍內最小/最大值的「值」。
        // *min_element / *max_element return the smallest/largest VALUE in the range.
        // begin()/end() 是 vector 的頭尾迭代器。/ begin()/end() are the container's iterators.
        int minVal = *min_element(nums.begin(), nums.end());
        int maxVal = *max_element(nums.begin(), nums.end());

        // range-for：依序取出 nums 裡的每個值 v，逐一標記存在。
        // range-for: iterate each value v in nums and mark it present.
        for (int v : nums) {
            seen[v] = true;  // 標記 v 出現過 / flag v as seen
        }

        vector<int> result;  // 動態陣列，會自動擴充 / dynamic array that grows as needed

        // 從 min 掃到 max（含兩端），收集沒被標記的值。
        // Sweep [min, max] inclusive; collect values not marked.
        for (int v = minVal; v <= maxVal; v++) {
            if (!seen[v]) {              // !seen[v] 代表 v 缺失 / not seen ⇒ missing
                result.push_back(v);     // 加到結果尾端 / append to result
            }
        }

        // 因為 v 遞增遍歷，result 天生排序，直接回傳。
        // Since v increases, result is already sorted; return it directly.
        return result;
    }
};

複雜度 / Complexity

• Time: O(n + R) — 一次掃描 nums（n 是陣列長度）建立標記與找 min/max，再走過範圍 [min, max]（R = max − min + 1）收集缺失。兩段都是線性，主導的是這兩個線性遍歷。因為值域固定在 1–100，實務上 R ≤ 100，整體非常快。 / One pass over nums (length n) plus one sweep over the range of size R; both linear.
• Space: O(M) — seen[] 大小固定為 101（因值域 1–100），是常數等級的額外空間；回傳陣列不計入額外空間。 / The seen[] array is a fixed 101 entries (values bounded 1–100), i.e. constant extra space; the output array is not counted.

Pitfalls & Edge Cases

• 忘記回傳長度 / forgetting *returnSize (C): LeetCode 靠 *returnSize 得知結果有幾個元素；忘了寫會讀到垃圾值導致錯誤。程式在最後一行 *returnSize = k; 正確設定。 / The harness reads the count from *returnSize; omitting it yields garbage. We set it at the end.
• 回傳區域陣列 / returning a local array (C): 若用 int result[...] 這種區域變數回傳，函式結束後記憶體失效。必須用 malloc。 / A stack array becomes invalid after return; use malloc.
• 標記陣列開太小 / off-by-one on seen size: 值可達 100，所以索引要到 100，陣列大小必須是 101（索引 0..100）。開成 100 會越界。 / Values reach 100, so seen needs 101 slots (indices 0..100), not 100.
• 邊界要含兩端 / inclusive bounds: 迴圈條件用 v <= maxVal（不是 <），否則會漏檢查 max 這一格（雖然 max 必存在，但保持邏輯一致最安全）。 / Use <= so the range is inclusive.
• 不需要額外排序 / no extra sort needed: 很多人會先排序 nums 再比對，但因為我們是從 min 到 max 遞增收集，結果已自然排序，省下一次排序。 / Iterating min→max yields a sorted result for free.
• 沒有缺失的情況 / no missing values: 例如 [7,8,6,9]，迴圈中每個 seen[v] 都為真，result 保持為空並正確回傳空清單。 / When everything is present, the result stays empty, as required.