问题：
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
For example,
Given nums = [0, 1, 3] return 2.
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
大意：
给出一个包含n个数字的数组，数字范围为 0, 1, 2, ..., n，寻找数组遗失的那个数字。
例子：
给出 nums = [0, 1, 3] 返回 2。
注意：
你的算法需要在线性时间复杂度内运行。能不能使用恒定的额外空间复杂度？
思路：
这道题就是找0~n中那个数字没出现。
题目说了要线性时间复杂度，所以不能对数组排序，又说要恒定的空间，所以不能创建一个新数组来记录出现过的数字。
其实既然知道了数字一定是 0, 1, 2, ..., n，只缺一个数字，我们可以求0~n的累加和，然后遍历数组，对数组中的数字也累加个和，相减就知道差的是那个数字了。
代码（Java）：
public class Solution {
public int missingNumber(int[] nums) {
int total = (1 + nums.length) * nums.length / 2;
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
}
return total - sum;
}
}
他山之石：
public int missingNumber(int[] nums) {
int xor = 0, i = 0;
for (i = 0; i < nums.length; i++) {
xor = xor ^ i ^ nums[i];
}
return xor ^ i;
}
这个方法还是利用异或的特性：相同的数字异或等于0，遍历过程中不断将 i 和数组中的数字异或，最后数组中有的数字都被异或成0了，最后剩下来的就是数组中没有的数字了。
合集：https://github.com/Cloudox/LeetCode-Record
