给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度O(n)。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2]
输出: 4

方法一：利用Map() Hash 结构

Map真的是解决算法问题的神器...

方法如下

var singleNumber = function(nums) {
    let l = nums.length
    let map = new Map()
    for(let i = 0; i < l; i++) {
        if (map.has(nums[i])) {
            map.delete(nums[i])
        } else {
               map.set(nums[i],i)
        }
    }
    return [...map.keys()][0]
};

方法二： 利用 对象或数组

这个本质其实跟Map差不多，以对象为例

var singleNumber = function(nums) {
    let l = nums.length
    let hash = {}
    for(let i = 0; i < l; i++) {
        if (hash[nums[i]] != undefined) {
            delete hash[nums[i]]
        } else {
            hash[nums[i]] = i
        }
    }
    return Object.keys(hash)[0]
};

方法三：利用 indexOf() lastIndexOf()

不过这个费时间比价多，严格来说不算 O(n)复杂度了

var singleNumber = function(nums) {
    let l = nums.length
    let map = new Map()
    for(let i = 0; i < l; i++) {
        if(nums.indexOf(nums[i])==nums.lastIndexOf(nums[i])){
            return nums[i]
        }
    }
};

方法四：异或运算！

看到这个就惊呆了，真的好方便！之前一直不会运用异或。

var singleNumber = function(nums) {
    let l = nums.length
    let val = 0
    for(let i = 0; i < l; i++) {
        val ^= nums[i]
    }
    return val
};

很精简的代码！执行效率也是这几个方法里最高的。

关于异或的运算法则

1）交换律：a ^ b = b ^ a
2）结合律：a ^ b ^ c = a ^ （b ^ c） = （a ^ b） ^ c
3）d = a ^ b ^ c  ==>  a = d ^ b ^ c
4）自反性：a ^ b ^ a = b