260. Single Number III

在一堆出现二的数字中返回两个只出现一次的数字。

Input:  [1,2,1,3,2,5]
Output: [3,5]

使用two sum的方法异或，慢慢

public int[] singleNumber(int[] nums) {
    int sum = 0;
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        set.add(num);
        sum ^= num;
    }
    for (int num : nums) {
        int other = sum ^ num;
        if (set.contains(other)) return new int[] {num, other};
    }
    return null;
}

所有的数字xor之后的二进制sum结果至少会有一位被置1，然后找到sum中最后一位被置1的位作为mask，然后使用这个mask遍历整个数组，计算res = mask ^ num，当res分别为0和其他数的时候，就可以把这两个数字筛选出来。

public int[] singleNumber(int[] nums) {
    int diff = 0;
    for (int num : nums) {
        diff ^= num;
    }

    int mask = (diff & -diff);

    int[] res = new int[2];
    for (int num : nums) {
        if ((num & mask) == 0) { 
            res[0] ^= num;
        } else {
            res[1] ^= num;
        }
    }
    return res;
}