136.只出现一次的数字

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

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

借助HashMap集合，可以将nums中出现的数字作为key记录到map中，有以下三种方法：

• 出现一次的value记为1，两次的记为2。再遍历找到value=1的key，输出。
• 出现一次的value记下，两次的remove掉这个key。再遍历直接输出留下的这个key。
• 将集合所有的数求和 * 2 减去nums和，剩下的即为answer，直接返回。

上面的三种方法都用到了集合，空间复杂度为线性。

使用位运算：异或，可以做到常数空间复杂度。

异或性质：

• A⊕B=AB`+A`B(定义)
• A⊕1=A`  A⊕0=A  A⊕A=0

方法1：

public int singleNumber(int[] nums){HashMap<Integer> map = new HashMap<>();for(int i : nums){if(map.containsKey(i)) map.put(i, 2);else map.put(i, 1);}for(int key : map.keySet()){if(map.get(key) == 1) return key;}return 0;
}

方法2：

public int singleNumber(int[] nums){HashMap<Integer> map = new HashMap<>();for(int i : nums){if(map.containsKey(i)) map.remove(i);else map.put(i, 1);}for(int key : map.keySet()){return key;}return 0;
}

方法3：

public int singleNumber(int[] nums){HashMap<Integer> map = new HashMap<>();int sumArr = 0;for(int i : nums){sum += i;if(map.containsKey(i)) map.put(i, 2);else map.put(i, 1);}int sumCol = 0;for(int key : map.keySet()){sumCol += key;}return cumCol * 2 - sumArr;
}

方法4：位运算，异或

public int singleNumber(int[] nums){int res = 0;// 0与任何数异或结果为那个数for(int i : nums){res ^= i;// 数组中相同的数异或结果为0}return res;
}