题目：
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
Example 1:
Input: [3,0,1]
Output: 2
Example 2:
Input: [9,6,4,2,3,5,7,0,1]
Output: 8
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
分析：
给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
最先想到将数组进行排序，再依次判定数和索引是否对应，首次不对应的索引便是缺失的数。不过由于需要对数组进行排序，这样时间复杂度就不会是线性的了。
也可以创建一个集合，将数组中元素添加进集合中，再从0到n对集合进行查询，不在集合内的便是缺失的数。不过这样空间复杂度就不是常数级的了。
我们知道所给的数的序列是从0到n，且只缺失一个数，根据高斯求和公式，可以快速求得0到n这n+1个数的和，再减去序列中的n个数，剩下的便是缺失的数。
还可以利用异或运算（XOR），我们知道对一个数进行两次完全相同的异或运算会得到原来的数，即
a ^ b ^ b = a
a ^ a = 0
根据题目我们知道，未缺失的数，在[0-n]和数组中各出现了一次，而缺失的数只在[0-n]中出现了一次，根据这个条件和异或的特性可以通过一次循环求得缺失数。
假设所给的序列为0,1,3,4，我们可以求得
missing = 4 ^ 0 ^ 0 ^ 1 ^ 1 ^ 2 ^ 3 ^ 3 ^ 4
= (4 ^ 4) ^ (0 ^ 0) ^ (1 ^ 1) ^ 2 ^ (3 ^ 3)
= 0 ^ 0 ^ 0 ^ 0 ^ 2
= 2
程序：
C++
//use math
class Solution {
public:
int missingNumber(vector<int>& nums) {
int n = nums.size();
int res = (+n)*n/;
for(int q:nums)
res -= q;
return res;
}
};
//use xor
class Solution {
public:
int missingNumber(vector<int>& nums) {
int res = nums.size();
for(int i = ; i < nums.size(); ++i){
res = res ^ i ^ nums[i];
}
return res;
}
};
Java
class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
int res = (1+n)*n/2;
for(int q:nums)
res -= q;
return res;
}
}
class Solution {
public int missingNumber(int[] nums) {
int res = nums.length;
for(int i = 0; i < nums.length; ++i){
res = res ^ i ^ nums[i];
}
return res;
}
}