給定包含 0,1,2,...,n 中 n 個不同數字的數組 nums（長度 n），找出缺失的那一個數字。要求：線性時間、常數空間。
示例：nums=[0,1,3] → 缺失 2
a ^ a = 0（自逆）a ^ 0 = aa ^ b ^ a = b（交換律、結合律）將 0~n 所有數異或，再與數組中所有數異或，成對抵消，剩下的就是缺失數。
public int missingNumber(int[] nums) {
int xor = 0;
for (int i = 0; i < nums.length; ++i) {
xor ^= i ^ nums[i]; // i 與 nums[i] 配對異或
}
return xor ^ nums.length; // 最後異或上 n (即 nums.length)
}
nums = [0,1,3], n=3
xor = 0
i=0: xor ^= 0 ^ 0 = 0
i=1: xor ^= 1 ^ 1 = 0
i=2: xor ^= 2 ^ 3 = 1 (0 ^ 2 ^ 3 = 1)
最終: xor ^= 3 (n) = 1 ^ 3 = 2 ← 缺失數
| 方法 | 時間 | 空間 | 備註 |
|---|---|---|---|
| 求和公式 | O(n) | O(1) | n*(n+1)/2 - sum(nums)，可能溢出 |
| 異或 | O(n) | O(1) | 無溢出風險，位運算極快 |
| 排序+掃描 | O(n log n) | O(1) 或 O(n) | 破壞原數組順序 |
| 哈希集合 | O(n) | O(n) | 空間不滿足要求 |
| 原地置換(循環排序) | O(n) | O(1) | 修改數組，邏輯較複雜 |
Missing Number 是位運算技巧的教科書級應用。異或法：無溢出、不修改數組、真正 O(1) 空間、代碼極簡。面試中優先給出異或解法，並能說明為什麼求和法可能溢出（大數據場景）。
