問題：
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個數(shù)字的數(shù)組，數(shù)字范圍為 0, 1, 2, ..., n，尋找數(shù)組遺失的那個數(shù)字。
例子：
給出 nums = [0, 1, 3] 返回 2。
注意：
你的算法需要在線性時間復(fù)雜度內(nèi)運行。能不能使用恒定的額外空間復(fù)雜度？
思路：
這道題就是找0~n中那個數(shù)字沒出現(xiàn)。
題目說了要線性時間復(fù)雜度，所以不能對數(shù)組排序，又說要恒定的空間，所以不能創(chuàng)建一個新數(shù)組來記錄出現(xiàn)過的數(shù)字。
其實既然知道了數(shù)字一定是 0, 1, 2, ..., n，只缺一個數(shù)字，我們可以求0~n的累加和，然后遍歷數(shù)組，對數(shù)組中的數(shù)字也累加個和，相減就知道差的是那個數(shù)字了。
代碼（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;
}
這個方法還是利用異或的特性：相同的數(shù)字異或等于0，遍歷過程中不斷將 i 和數(shù)組中的數(shù)字異或，最后數(shù)組中有的數(shù)字都被異或成0了，最后剩下來的就是數(shù)組中沒有的數(shù)字了。
合集：https://github.com/Cloudox/LeetCode-Record
