268. Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity? 268. Missing Number

---

从0,1…n这n+1个数中选n个不同的数，问哪一个数没有选。需要使用线性时间复杂度和常数空间复杂度。因为知道n，所以就知道这n+1个数的和，减去选出来的n个数的和，就是那个没有被选中的数。
完整代码如下：

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

本代码提交AC，用时36MS。