一、题目描述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
二、思路讲解与代码实现
首先很容易想到的是排序，排序了之后，只存在一个的数字（后面简称为目标数字）的左右必然都不是与他相等的数字。
这个时候需要考虑目标数字在最前面或最后面的情况，需要单独处理。
class Solution { public int singleNumber(int[] nums) { if(nums.length==1){ return nums[0]; } Arrays.sort(nums); int len = nums.length; //当目标数字在第一个的时候 if(nums[0]!=nums[1]){ return nums[0]; } for(int i=1; i<len-3; i++){ //如果一个数跟他左右的元素都不一样，则是我们要找的数 if(nums[i]!=nums[i+1]){ if(nums[i+1]!=nums[i+2]){ return nums[i+1]; } } } //当目标数字在最后一个的时候 if(nums[len-1]!=nums[len-2]){ return nums[len-1]; } return 0; } }
时间复杂度： O(NlogN)
空间复杂度： O(1)
排序的时间复杂度有些过高了，我们如何能够通过一遍遍历就能够找到目标数呢？
可以使用HashSet或HashMap。
使用 HashMap 可以记录每个数字的出现次数，然后找到次数为1的即可。
使用 HashSet 时，如果遇到重复数字不能添加的情况，就把set中的那个重复数字也删去。因为一个数字最多出现两次，出现第二次的时候没有添加进set，并且还把第一次的添加给删掉了，所以set最后只会留下这个只出现过一次的数字。
下面是使用set的实现：
class Solution { public int singleNumber(int[] nums) { Set<Integer> set = new HashSet<>(); for(int i=0;i<nums.length; i++){ //如果重复了，就把原本set里的那个元素也删掉 删到最后只会剩下一个元素，就是单个的那个元素 if(!set.add(nums[i])){ set.remove(nums[i]); } } //此时set中只有一个元素 for(Integer i : set){ return i; } return 0; } }
时间复杂度： O(N)
空间复杂度： O(N)
这个方法需要使用线性级的空间，我们可不可以再做一下优化，如何在只遍历一遍的情况下，只使用常量级的空间呢？
这就需要使用异或运算了。我们知道，两个相同的数进行异或运算，结果为0， 而0和任意不是0的数字异或，结果仍是这个数字。那么我们就将所有的数字进行异或运算，每个出现两次的数字都抵消为0，最后得到的结果就是目标数了。
class Solution { public int singleNumber(int[] nums) { int res = 0; for(int num : nums){ res = res ^ num; } return res; } }
时间复杂度： O(N)
空间复杂度： O(1)
