136. 只出现一次的数字

题目让我们在一个数组里面，找到一个没有重复元素的元素。首先我想到的是使用哈希表，统计每个元素的数量，如果这个元素的数量是1,自然就是出现只有一次的数字，代码如下：

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        hs=dict()
        for i in nums:
            hs[i]=hs.get(i,0)+1
        for key in hs.keys():
            if hs[key]==1:
                return key

虽然是两个for循环吧，但是也是线性时间复杂度，但是用了哈希表，空间复杂度就是O（n）了，题目是让我们用常数级的空间复杂度。

但是这个题如果用比较常规的做法，空间复杂度是没办法优化的，就是需要引入一个位运算符，异或运算符。它的规则是两个数异或，不同的时候为真，相同的时候为假。所以就有几个神奇的特性。

1. 一个数字异或0,还是它本身。x^0=x，例如数字9,二进制为1001，当某一位为1的时候和0异或，结果为1,当某一位为0的时候，和0异或，结果是0,所以运算完之后，每一位都不会改变，依然是1001.还是数字9

2. 两个相同的数字进行异或，结果为0,x^x=0,例如数字9,二进制为1001,异或是相同为假，每一位肯定都是相同的，结果就0000,也就是0.

3. 异或是满足交换律的,x^y^x=x^x^y.

利用这三点，我们就可以在线性时间复杂度，常数空间复杂度解决这个问题了。直接对所有的数字进行一个异或，就可以得到答案。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res=0
        for i in nums:
            res=res^i
        return res