136. Single Number

題目描述:

給定一個非空的整數陣列 nums，其中每個元素都出現兩次，只有一個元素只出現一次。找出這個只出現一次的元素。

你必須實現一個具有線性運行時間複雜度的解法，並且只使用恆定的額外空間。

Example:
Input: nums = [4,1,2,1,2]
Output: 4

解題思路:
這道題目要求我們在 O(n) 的時間複雜度和 O(1) 的空間複雜度下找到唯一出現一次的數字，且不能使用像 map 這樣的資料結構來儲存計數資訊。意思是，我們只能遍歷一次陣列，並且要在不增加額外儲存空間的情況下完成這個任務。

由於每個元素都會出現兩次，只有一個數字出現一次，我們可以利用一個特殊的運算方式：XOR（互斥運算） 來解決這個問題。XOR 有一些重要的特性可以幫助我們達到目標：

1. A ^ A = 0：同樣的數字經過 XOR 會相互抵消變成 0。
2. A ^ 0 = A：任何數字和 0 做 XOR，結果還是它自己。
3. A ^ B = B ^ A：XOR 是交換律的，也就是說 XOR 的運算順序不影響結果。

透過上面三個公式，當我們依次遍歷整個陣列，將每個數字和一個變數進行XOR操作時，出現兩次的數字會相互抵消變成 0，而唯一出現一次的數字，最後就會保留在變數中。這樣不需要額外的儲存空間，且只需遍歷一次陣列即可。

var singleNumber = function(nums) {
    let single = 0;
    
    for (let num of nums) {
        single ^= num;
    }
    
    return single;
};

時間複雜度: O(n)，其中 n 是陣列的長度。
空間複雜度: O(1)，只使用了一個變數來存儲結果，因此不會佔用額外的空間。

總結:
這道題目可以歸類為「XOR」（互斥運算）。對於初次見到這題的讀者來說，可能會覺得這麼巧妙的方法很難想到，因為使用 XOR 來解題並不直觀。不過，學習完這題後，讀者會對 XOR 運算的特殊性有更深的理解，尤其是它能消除成對的數字，僅留下唯一不重複的數字。這樣的技巧在之後的 LeetCode 題目中還會被用到，只是會以不同的形式出現。因此，掌握XOR的應用將有助於讀者解決更多類似的問題，特別是在要求常量空間和線性時間複雜度的題目中。