解題說明
Find All Numbers Disappeared in an Array
題目描述：
給定一個長度為 n 的陣列 nums，其中元素值在 [1, n] 範圍內，某些數字出現了兩次而某些沒有出現。找出 [1, n] 中所有未出現的數字。要求在不使用額外空間的情況下完成（O(1) 額外空間，不計輸出陣列）。
解題思路：
利用陣列本身作為雜湊表。由於值域恰好是 [1, n]，可以將值 x 對應到索引 x-1。
- 第一次遍歷：對每個值
nums[i]，將索引|nums[i]| - 1處的元素標記為負數（取絕對值避免重複標記影響）。 - 第二次遍歷：若
nums[i]仍為正數，代表i+1從未出現過，加入結果。
這樣不需要額外空間，也不破壞原始數據（可透過取絕對值還原）。
C++ 解法
複雜度分析
時間複雜度：O(n) — 兩次線性遍歷。
空間複雜度：O(1) — 不計輸出陣列，只使用常數額外空間。原地修改輸入陣列。
虛擬碼
1. For each element nums[i]: a. Compute index = |nums[i]| - 1 b. If nums[index] > 0, negate it: nums[index] = -nums[index] 2. Initialize result = [] 3. For each index i from 0 to n-1: a. If nums[i] > 0, append i+1 to result 4. Return result
其他解法
Cyclic Sort（循環排序）：將每個數字放到正確位置（nums[i] 放到 nums[nums[i]-1]）。排序完後，nums[i] != i+1 的位置即為缺失數字。時間 O(n)，空間 O(1)。比標記法更直觀但需要更多 swap 操作。
HashSet 法 O(n) 時間 + O(n) 空間：將所有出現的數字加入集合，再遍歷 1 到 n 找缺失的。簡單直接但使用了 O(n) 額外空間，不滿足進階要求。
延伸思考
- 如何找出所有出現兩次的數字？（LeetCode 442）用類似的標記技巧。
- 若只有一個數字缺失，能否用數學方法（高斯求和）在 O(1) 空間解決？（LeetCode 268）
- 「將值對應到索引」的技巧還能應用在哪些問題上？（LeetCode 41 First Missing Positive）