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?

（1）

class Solution {public:    int missingNumber(vector
        
         & nums) {        int n = nums.size(), ans = 0;        for(int i = 0; i < n; i++)        {            ans ^= nums[i] ^ (i+1);        }        return ans;    }};
        

异或0-n，异或nums。

异或0还等于原来的数。

（2）

class Solution {public:    int missingNumber(vector
        
         & nums) {        int n = nums.size(), sum = n*(n+1) / 2;        for(int i = 0; i < n; i++)        {            sum -= nums[i];        }        return sum;    }};
        

求和相减。