LeetCode刷题实战260：只出现一次的数字 III-技术圈

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 只出现一次的数字 III，我们先来看题面：

https://leetcode-cn.com/problems/single-number-iii/

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

Follow up: Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。你可以按任意顺序返回答案。

进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

示例

示例 1：

输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。

示例 2：

输入：nums = [-1,0]
输出：[-1,0]

示例 3：

输入：nums = [0,1]
输出：[1,0]

解题

我们知道两个相同的数异或之后就为0，所以对于nums数组中的所有数，异或之后的结果就是那两个只出现一次的数异或的值。

这个值必然不为0（因为这两个数是不同的），所以这个数的二进制表示里，从低位往高位必然有一位1，这一位是1，说明这两个数在这一位的二进制表示不同（因为这个数是异或得到的），我们可以以与这一位的1与的结果为1还是为0，把nums数组的元素分为两组，则这两个不同的数必然被分在不同的组。又由于相同的数异或为0，所以同一组的数全部进行异或操作，最后两组剩下的值就分别是这两个不同的数了。

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int> res(2, 0); // 分为两组
        int sum = 0; // sum是nums所有元素异或的结果
        for(int i = 0; i < nums.size(); ++i) {
            sum ^= nums[i];
        }
        int firstOne = sum & (-sum); // 得到最低位的1，sum & (-sum)这是一个常见的技巧
        for(int i = 0; i < nums.size(); ++i) {
            if(firstOne & nums[i]) { // 如果和firstOne相与为1，分到第一组（并且第一组所有元素进行异或操作）
                res[0] ^= nums[i];
            } else { // 否则到第二组（并且第二组所有元素进行异或操作）
                res[1] ^= nums[i];
            }
        }
        return res;
    }
};