1. 題目鏈接

LeetCode 268. 丟失的數字

---

2. 題目描述

給定一個包含 [0, n] 范圍內 n 個不同整數的數組 nums（實際長度為 n），找出數組中缺失的那個數字。
示例：

• 輸入：nums = [3,0,1] → 輸出：2（缺失數字為 2）
• 輸入：nums = [0,1] → 輸出：2（缺失數字為 2）

---

3. 示例分析

1. 缺失中間值：
   • nums = [0,1,3,4] → 缺失 2。
2. 缺失最大值：
   • nums = [0,1,2] → 缺失 3（數組長度 n=3，范圍為 [0,3]）。
3. 空數組：
   • 若 nums = [] → 缺失 0（題目保證 n ≥ 1，實際無需處理）。

---

4. 算法思路

核心思想：異或運算的歸零律與恒等律

1. 異或性質：
   • 歸零律：a ^ a = 0
   • 恒等律：a ^ 0 = a
   • 交換律：a ^ b = b ^ a
2. 問題轉化：
   • 假設完整數組為 [0,1,2,...,n]，實際數組 nums 缺少其中一個數。
   • 對完整數組和實際數組進行異或運算，重復的數會被抵消，最終結果為缺失值。

實現步驟：

1. 遍歷實際數組：將所有元素異或到結果 ret。
2. 遍歷完整數組：將 [0,1,...,n] 中的每個數異或到 ret。
3. 最終結果：ret 即為缺失的數字。

---

5. 邊界條件與注意事項

1. 輸入數組有效性：
   • 題目保證數組元素唯一且范圍正確，無需額外處理重復或越界值。
2. 缺失最大值的處理：
   • 若缺失 n，第二個循環中 i 的范圍為 0~n，仍能正確異或得到結果。
3. 異或運算順序無關性：
   • 異或滿足交換律，遍歷順序不影響最終結果。

---

6. 代碼實現

class Solution 
{
public:int missingNumber(vector<int>& nums) {int ret = 0;// 第一輪異或：處理實際數組for (int num : nums) ret ^= num;// 第二輪異或：處理完整數組 [0, 1, ..., n]for (int i = 0; i <= nums.size(); i++) ret ^= i;return ret;}
};

---

算法分步解析

1. 初始化結果變量：

   int ret = 0;
   

   • ret 初始為 0，因為 0 ^ a = a。

2. 第一輪異或遍歷實際數組：

   for (int num : nums) ret ^= num;
   

   • 假設實際數組為 [3,0,1]，則 ret 結果為 3 ^ 0 ^ 1 = 2。

3. 第二輪異或遍歷完整數組：

   for (int i = 0; i <= nums.size(); i++) ret ^= i;
   

   • 完整數組為 [0,1,2,3]，此時 ret 計算為 2 ^ 0 ^ 1 ^ 2 ^ 3 = 3。

4. 返回結果：

   return ret;
   

   • 最終結果為 3，即缺失的數字。

---

與暴力枚舉法的對比

方法	時間復雜度	空間復雜度	核心思想
異或法	O(n)	O(1)	利用異或抵消重復元素
哈希表法	O(n)	O(n)	存儲已出現元素，查找缺失值
數學求和法	O(n)	O(1)	計算理論總和與實際和的差值
暴力枚舉法	O(n2)	O(1)	遍歷檢查每個數是否在數組中

---

異或法的優勢

1. 無額外空間：僅需常數空間，適合內存敏感場景。
2. 避免溢出風險：相較于求和法，異或法無需處理大數溢出問題。
3. 高效性：兩次線性遍歷即可解決問題。

---

總結

異或法通過巧妙的位運算，將時間復雜度控制在 O(n)，同時避免使用額外空間，是解決“缺失數字”類問題的最優方案。其核心在于利用異或運算的數學性質，將重復元素抵消，最終定位缺失值。實際應用中，該方法還可擴展至其他需要“去重”或“找不同”的場景，例如只出現一次的數字等問題。

關鍵點：

• 異或運算的歸零律和恒等律是算法的基礎。
• 兩次遍歷分別處理實際數組和完整數組，確保所有元素成對抵消。