消失的两个数字

给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？

题目链接：https://leetcode.cn/problems/missing-two-lcci/

这道题严格来说并不是一道算法题，我感觉它的解法中，一种像是计算机组成中二进制的知识，一种是数学知识

求和

这种方法是纯数学方法，

• 我们知道1～N的和是$\frac{N(N+1)}{2}$,然后我们可以通过遍历的方法求出提供的N-2个数字的和，通过相减，我们可以得到缺失的两个数字的和，假设为sumTwo，缺失的两个数分别为a和b
• 缺失的两个数字是不相同的，所以一个大一个小，也就是说一个小于二者的平均值，一个大于二者的平均值，假设这个平均值为limit，则$limit = \frac{sumTwo}{2}$
• 然后再根据是否小于limit将1～N分为两部分，则a在1～limit之间，我们只需要计算1～limit的和，即$\frac{limit(limit+1)}{2}$与提供的数组中1～limit的数字的和之间的差值，其实就是a。求b同理

var missingTwo = function(nums) {
    const N = nums.length + 2;
    const sumTwo = (N * (N + 1)) / 2 - nums.reduce((pre, cur) => (pre + cur), 0);
    const limit = Math.floor(sumTwo / 2);
    let sumBefore = 0;
    for(const num of nums) {
        if (num <= limit) {
            sumBefore += num;
        }
    }
    const one = (limit * (limit + 1)) / 2 - sumBefore;
    return [one, sumTwo - one];
};

利用位运算

这种思路和上面的求和思路有些类似，都是先求出缺失的两个数字的合并后的结果，然后根据合并的结果把提供的数字分成两部分，缺失的两个数字分别在两个部分中。

由于从 1 到 n 的整数中有两个整数消失，其余每个整数都在数组中出现一次，因此数组的长度是 n - 2。在数组中的 n - 2 个数后面添加从 1 到 n 的每个整数各一次，则得到 2n−2 个数字，其中两个在数组中消失的数字各出现一次，其余每个数字各出现两次。

假设数组 nums 中消失的两个数字分别是$x_1$,$x_2$ 。如果把上述 2n−2 个数字全部异或起来，得到结果 x，那么一定有：

$$x = x_1 \bigoplus x_2$$

其中$\bigoplus$ 表示异或运算。这是因为 nums 中出现两次的元素都会因为异或运算的性质$a \bigoplus b \bigoplus b = a$ 抵消掉，那么最终的结果就只剩下$x_1$,$x_2$的异或和。

显然$x \ne 0$，因为如果 x=0，那么说明$x_1 = x_2$ ,$x_1$,$x_2$就不是在上述 2n - 2 个数字中只出现一次的数字了。因此，我们可以使用位运算 x & -x 取出 x 的二进制表示中最低位那个 1，设其为第 l 位，那么$x_1$,$x_2$中的某一个数的二进制表示的第 l 位为 0，另一个数的二进制表示的第 l 位为 1。在这种情况下，$x_1 \bigoplus x_2$的二进制表示的第 l 位才能为 1。

这样一来，我们就可以把从 1 到 n 的所有整数分成两类，其中一类包含所有二进制表示的第 l 位为 0 的数，另一类包含所有二进制表示的第 l 位为 1 的数。可以发现：

对于任意一个在数组 nums 中出现一次的数字，这些数字在上述 2n−2 个数字中出现两次，两次出现会被包含在同一类中；

对于任意一个在数组 nums 中消失的数字，即$x_1$,$x_2$ ，这些数字在上述 2n - 2 个数字中出现一次，会被包含在不同类中。

因此，如果我们将每一类的元素全部异或起来，那么其中一类会得到$x_1$另一类会得到$x_2$。这样我们就找出了这两个只出现一次的元素。

var missingTwo = function(nums) {
    let xorsum = 0;
    let n = nums.length + 2;
    for (const num of nums) {
        xorsum ^= num;
    }
    for (let i = 1; i <= n; i++) {
        xorsum ^= i;
    }
    let type1 = 0, type2 = 0;
    const lsb = xorsum & (-xorsum);
    for (const num of nums) {
        if (num & lsb) {
            type1 ^= num;
        } else {
            type2 ^= num;
        }
    }
    for (let i = 1; i <= n; i++) {
        if (i & lsb) {
            type1 ^= i;
        } else {
            type2 ^= i;
        }
    }
    return [type1, type2];
};