解題說明
Single Number
題目描述：給定一個非空整數陣列，其中每個元素都出現兩次，只有一個元素出現一次。要求在 O(n) 時間、O(1) 空間內找出那個只出現一次的元素。
解題思路：利用 XOR（互斥或）的特性：
a XOR a = 0（相同的數字 XOR 結果為 0）a XOR 0 = a（任何數與 0 XOR 結果為自身）- XOR 滿足交換律與結合律
將陣列中所有元素做 XOR 運算。出現兩次的數字互相抵銷變為 0，最終剩下的就是只出現一次的那個元素。例如 [4, 1, 2, 1, 2]：4 XOR 1 XOR 2 XOR 1 XOR 2 = 4 XOR (1 XOR 1) XOR (2 XOR 2) = 4 XOR 0 XOR 0 = 4。
C++ 解法
複雜度分析
時間複雜度：O(n) — 對陣列進行一次線性掃描，n 為元素個數。
空間複雜度：O(1) — 只使用一個整數變數儲存 XOR 累積結果，不需要雜湊表或其他額外空間。
虛擬碼
1. Initialize result = 0 2. For each num in nums: a. result = result XOR num 3. Return result
其他解法
方法一：雜湊表計數
使用 unordered_map 統計每個數字的出現次數，最後找出次數為 1 的元素。時間複雜度 O(n)，但空間複雜度為 O(n)，不符合題目 O(1) 空間的要求。
方法二：數學公式
計算所有不重複元素的總和（用 unordered_set 去重）的兩倍，減去陣列所有元素的總和，差值即為只出現一次的元素（2 * sum(set) - sum(array)）。時間複雜度 O(n)，空間複雜度 O(n)，同樣不符合最優空間需求。
延伸思考
- 如果陣列中有一個元素出現一次、其餘元素出現三次，如何在 O(n) 時間、O(1) 空間找出該元素？（LeetCode 137）
- 如果陣列中有兩個元素各只出現一次，其餘出現兩次，如何找出這兩個元素？（LeetCode 260）
- XOR 在密碼學與資料傳輸中有哪些實際應用場景？例如簡單的串流加密或奇偶校驗位的計算。