136. Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

这道题目可采用hash map的思想来解，时间复杂度为O(n)。 若要求不能使用extra memory，则需要位操作的技巧。 注意到两个相同int的抑或操作(^)为0，0与任意int抑或即int本身。 因此可将nums中所有数进行抑或操作，最后结果即为single number。

public class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for(int i = 0; i < nums.length; i++) {
            res ^= nums[i];
        }
        return res;
    }
}