136. Single Number

題目網址：https://leetcode.cn/problems/single-number/

題意：給一非空的 array nums, 當中只有一個數 n1 只出現一次, 找出 n1。

Solution：

想法：利用 XOR 的特性, a ^ a = 0 且 0 ^ b = b, 還有交換性
e.g. b ^ a ^ b = a ^ (b ^ b) = a ^ 0 = a

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (const auto& num : nums) {
            res ^= num;
        }
        return res;
    }
};

• time：$O(n)$ ➔ 遍歷 nums
• space：$O(1)$ ➔ 只需要常數空間