消失的數字

數組nums包含從0到n的所有整數，但其中缺了一個。請編寫代碼找出那個缺失的整數。你有辦法在 O(n) 時間內完成嗎？
示例：
輸入：[3,0,1]
輸出：2

int missingNumber(int* nums, int numsSize) {}

分析

本題對時間復雜度的要求是O(n)。
利用異或相同為0，不同為1；也就是相同的數異或為0；任何數異或0，結果為原來的數。
思路1：單身狗思想：將數組中所有數異或起來的值，再與0~numsSize之間的值異或，最后的結果就是沒出現過的數。

注：
異或符合交換律和結合律
1 ^ 1 ^ 3 = 3
1 ^ 3 ^ 1 = 3

思路2：公式法：0~numsSize的和減數組元素的和，結果就是沒出現過的數。

代碼

代碼1

int missingNumber(int* nums, int numsSize) 
{int val = 0;for(int i=0; i<numsSize; i++){val ^= nums[i];}for(int i=0; i<=numsSize; i++){val ^= i;}return val;
}

代碼解釋：
因為任何數異或0為原數，所以使用val=0為原始值。
又因為異或符合交換律和結合律，所以
val=0 ^ ( 0 ^ 1 ^ 3 ) ^ ( 0 ^ 1 ^ 2 ^ 3 ) = 2

代碼2：

int missingNumber(int* nums, int numsSize) 
{int sum = numsSize*(numsSize+1)/2;for(int i=0; i<numsSize; i++){sum -= nums[i];}return sum;
}