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：0-n求和，再减去数组元素的总和，即为缺失元素。
思路2：亦或操作。两个相同的数亦或结果为0，一个不为0的数与0亦或，其值为本身。

实现代码

C++代码1：

// Runtime: 36 ms
// 代码已AC，但求和有溢出风险。
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int len = nums.size();
        int sum = 0;
        for_each(nums.begin(), nums.end(), [&sum](int n){ sum += n; });
        int total = (len + 1) / 2.0 * (0 + len);
        return total - sum;
    }
};

C++代码2：

// Runtime: 36 ms
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int miss = nums[0] ^ 0;
        for (int i = 1; i < nums.size(); i++) {
            miss ^= nums[i];
            miss ^= i;
        }

        return miss ^= nums.size();
    }
};

Java代码1：

// Runtime: 1 ms
public class Solution {
    public int missingNumber(int[] nums) {
        int sum = (int)((nums.length + 1) / 2.0 * nums.length);
        for (int n : nums) {
            sum -= n;
        }

        return sum;
    }
}

Java代码2：

// Runtime: 1 ms
public class Solution {
    public int missingNumber(int[] nums) {
        int miss = nums[0] ^ 0;
        for (int i = 1; i < nums.length; i++) {
            miss ^= nums[i];
            miss ^= i;
        }

        return miss ^= nums.length;
    }
}