力扣：268. 丢失的数字

难度 简单

题目描述：

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1：

输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 2：

输入：nums = [0,1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 3：

输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。

示例 4：

输入：nums = [0]
输出：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。

提示：

• n == nums.length
• \(1\) <= n <= \(104\)
• \(0\) <= nums[i] <= n
• nums 中的所有数字都 独一无二

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/missing-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

由于给出的数组是无序的，只能遍历整个数组就可以知道缺失的数组了。但是分别存储每个数字出现的次数消耗的内存将增多，所以只能尝试使用空间更小的方法存储。

已知任意整数 n ^ n == 0 ，所以只需要将该区间中的所有整数进行异或，再与数组中的数进行异或，设数组中未出现的数字为 t ：

\(\left(0 \oplus 1 \oplus 2 \cdots \oplus t \oplus \cdots \oplus n\right)\oplus\left(num\left[0\right] \oplus num\left[1\right] \oplus num\left[2\right] \oplus \cdots \oplus num\left[n-1\right]\right)\)

\(=\left(0 \oplus 0\right) \oplus \left(1 \oplus 1\right) \oplus \cdots \oplus t \oplus \cdots \oplus \left(n \oplus n\right)\)

\(=0 \oplus 0 \oplus 0 \oplus \cdots \oplus t\)

\(=t\)

则可按如下方式编写代码：

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();

        for (int i = 0; i < nums.size(); ++i) {
            n ^= i;
            n ^= nums[i];
        }
        
        return n;
    }
};

用时和内存的情况是16ms/17.4MB，超过了76.358%/91.550%。

但是这道题还可以用单纯的加减法计算：从 [0,n] 的和中减去数组中的数字，最后剩下的就是 t 。但是加减法的方式慢了一些。