448. Find All Numbers Disappeared in an Array

📘 題目敘述

給你一個長度為 n 的整數陣列 nums，其中 nums[i] 的值都介於 [1, n] 之間。

請回傳所有在範圍 [1, n] 中、但沒有出現在 nums 裡的整數。

條件限制

n == nums.length
1 <= n <= 10^5
1 <= nums[i] <= n

🧠 解題思路

這題的想法很直接。

因為題目要我找的是：

1 ~ n 裡哪些數字沒有出現在 nums

所以我就先開一個布林陣列 count，專門記錄每個數字有沒有出現過。

做法是：

掃一次 nums
如果看到數字 i
- 就把 count[i] = true

這樣掃完之後：

count[x] == true 代表數字 x 有出現
count[x] == false 代表數字 x 沒出現

接著再從 1 掃到 n：

哪些位置還是 false
那些數字就是消失的數字，把它放進答案陣列即可

也就是說，這題的核心就是：

用一個布林陣列記錄 1 ~ n 中哪些數字有出現，最後把沒被標記到的數字收集起來。

所有變數

nums：輸入陣列
n：陣列長度
count：布林陣列，count[x] 表示數字 x 是否出現過
ans：存所有沒有出現在 nums 裡的數字

🪜 主要流程步驟

1. 先取得陣列長度 n

int n = nums.size();

這一步先把 nums 的長度存起來，因為題目保證：

數字範圍就是 1 ~ n

所以後面開記錄陣列和掃描缺失數字時都會用到 n。

2. 開一個布林陣列 count，記錄每個數字有沒有出現

vector<bool> count(n + 1, false);

這裡開成 n + 1，是因為我想直接用數字本身當 index。

也就是說：

count[1] 對應數字 1
count[2] 對應數字 2
...
count[n] 對應數字 n

而 count[0] 不會用到。

一開始全部設成 false，表示還沒看到任何數字。

3. 掃一次 nums，把出現過的數字標記成 true

for (int i : nums) {
    count[i] = true;
}

這一步就是把所有有出現的數字做記號。

例如如果 nums 裡有：

那就把：

count[4] = true
count[3] = true
count[2] = true

這樣掃完整個 nums 後，就能知道哪些數字有出現，哪些沒有。

4. 再從 1 掃到 n，把沒有出現的數字收進 ans

vector<int> ans;
for (int j = 1; j <= n; j++) {
    if (!count[j]) {
        ans.push_back(j);
    }
}

這一步是在檢查：

1 ~ n 每個數字是不是都出現過

如果 count[j] 仍然是 false，就代表數字 j 沒有出現在 nums 裡，所以它就是答案之一。

這時就把 j 放進 ans。

5. 最後回傳 ans

return ans;

當 1 ~ n 全部檢查完後，ans 裡放的就是所有缺失的數字，直接回傳即可。

⏱️ 複雜度

設 n = nums.length。

時間複雜度：O(n) 掃一次 nums 做標記，再掃一次 1 ~ n 找缺失數字。
空間複雜度：O(n) 額外使用了一個長度為 n + 1 的布林陣列 count。

💻 程式碼實作

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int n = nums.size();
        vector<bool> count(n + 1, false);
        for (int i : nums) {
            count[i] = true;
        }
        vector<int> ans;
        for (int j = 1; j <= n; j++) {
            if (!count[j]) {
                ans.push_back(j);
            }
        }
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/