题目描述
给定一个包含 [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 中。

方法一：数学
将从 0 到 n 的全部整数之和记为 total，根据高斯求和公式，有：total = n(n+1)/2
将数组 nums 的元素之和记为 arrSum，则 arrSum 比 total 少了丢失的一个数字，因此丢失的数字即为 total 与 arrSum 之差。或者不断减去数组中的元素也是一样的。

int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int total = n * (n + 1) / 2;
        int arrSum = 0;
        for (int i = 0; i < n; i++) {
            arrSum += nums[i];
        }
        return total - arrSum;
    }

方法二：位运算
数组 nums 中有 n 个数，在这 n 个数的后面添加从 0 到 n 的每个整数，则添加了 n+1 个整数，共有 2n+1 个整数。
在 2n+1 个整数中，丢失的数字只在后面 n+1 个整数中出现一次，其余的数字在前面 n 个整数中（即数组中）和后面 n+1 个整数中各出现一次，即其余的数字都出现了两次。
根据出现的次数的奇偶性，可以使用按位异或运算得到丢失的数字。按位异或运算 ⊕ 满足交换律和结合律，且对任意整数 x 都满足 x⊕x=0 和 x⊕0=x。
由于上述 2n+1 个整数中，丢失的数字出现了一次，其余的数字都出现了两次，因此对上述 2n+1 个整数进行按位异或运算，结果即为丢失的数字。

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

方法三：排序
将数组排序之后，即可根据数组中每个下标处的元素是否和下标相等，得到丢失的数字。
由于数组的长度是 n，因此下标范围是 [0,n−1]。假设缺失的数字是 k，分别考虑以下两种情况：
(1)当 0≤k<n 时，对任意 0≤i<k，都有 nums[i]=i，由于 k 缺失，因此 nums[k]=k+1，k 是第一个满足下标和元素不相等的下标；
(2)当 k=n 时，0 到 n−1 都没有缺失，因此对任意 0≤i<n，都有 nums[i]=i。
根据上述两种情况，可以得到如下方法得到丢失的数字：
(1)从左到右遍历数组 nums，如果存在 0≤i<n 使得 nums[i]≠i，则缺失的数字是满足 nums[i]≠i 的最小的 i；
(2)如果对任意 0≤i<n，都有 nums[i]=i，则缺失的数字是 n。

int missingNumber(vector<int>& nums) {
    sort(nums.begin(),nums.end());
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        if (nums[i] != i) {
             return i;
        }
    }
    return n;
}

方法四：哈希集合
使用哈希集合，可以将时间复杂度降低到 O(n)。
首先遍历数组 nums，将数组中的每个元素加入哈希集合，然后依次检查从 0 到 n 的每个整数是否在哈希集合中，不在哈希集合中的数字即为丢失的数字。由于哈希集合的每次添加元素和查找元素的时间复杂度都是 O(1)，因此总时间复杂度是 O(n)。

int missingNumber(vector<int>& nums) {
        unordered_set<int> set;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            set.insert(nums[i]);
        }
        int missing = -1;
        for (int i = 0; i <= n; i++) {
            if (!set.count(i)) {
                missing = i;
                break;
            }
        }
        return missing;
}

方法五：异或改进
首先证明(n)⊕(n+1)⊕(n+2)⊕(n+3)=0，其中(n≡0(mod4))
先来观察一组数字，{0,1,2,3}
00⊕01⊕10⊕11=0,
对于任意由{n,n+1,n+2,n+3}，其中(n≡0(mod4))，是否有同样的关系？

运用上述性质解答
对于本题中的n个数字，先补充k个数字(值分别为n+1,…,n+k)，使得(n+k)≡3(mod4)，然后对所有值求异或即为解。

int missingNumber(vector<int>& nums) {
        int res = 0;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            res ^= nums[i];
        }
        int k = 0;
        while((n + k)% 4 != 3){
            k ++;            
            res ^= (n + k);
        }
        return res;
    }