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

异或操作

异或运算满足结合律，对一个数字进行两次完全相同的异或运算会返回原来的数。数组中有 n 个数，并且缺失的数在 [0, n]中，因此可以先到得到 [0, n]的异或值，再将结果对数组中的每一个数进行一次异或运算。

未缺失的数在[0, n]中各出现一次，异或后得到 0。缺失的数只在 [0, n]中出现一次，在数组中没有出现，最终的异或结果就是这个缺失的数字。

• 时间复杂度O(n)，空间复杂度O(1)
• Runtime: 76 ms, faster than 88.62%
• Memory Usage: 41.5 MB, less than 33.69%

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
  let missing = nums.length;
  for (let i = 0; i < nums.length; i++) {
    missing ^= i ^ nums[i];
  }
  return missing;
};

高斯公式

• 时间复杂度 O(N)，空间复杂度O(1)
• Runtime: 88 ms, faster than 52.81%
• Memory Usage: 41.3 MB, less than 54.49%

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
  const total = nums.length * (nums.length + 1) / 2;
  let sum = 0;
  for (let num of nums) {
    sum += num;
  }
  return total - sum;
};