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?

Credits:

Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

非常妙的一题

使用xor操作, nums中给出的n个数其范围应该在[0, n]之间（共n+1个）即0.1.2.3...n，然后抽掉了一个数，形成nums中的数字（共n个）。所以使用0.1.2.3...n这n+1个数字和数组内各个元素做xor，n+n+1= 2n+1，这样下来必有一个数找不到和他一致的xor为零的数，这个数就是nums数组中缺少的那个

class Solution {public:    int missingNumber(vector
    
     & nums) {        int len = nums.size();        int pos = 0;        for (int i=0; i
    

或者也可以使用数列求和公式

class Solution {public:    int missingNumber(vector
    
     & nums) {        int len = nums.size();                double sum_should = (0 + len) * (len + 1) / 2.0;        double sum_actual = 0;        for (int e : nums) {            sum_actual += e;        }        return sum_should - sum_actual;    }};