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& 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& 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;
    }
}