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.
Subscribe to see which companies asked this question
//思路首先：
//我真服了这个题，题意理解错了，我还以为是干嘛呢！
//后来才明白原来是随机从0到size()选取了一些数，其中有一个丢失了，草
//别人的算法：数学推出，0到size()的总和减去当前数组和sum
class Solution {
public:
int missingNumber(vector<int>& nums) {
int sum = 0;
for(int num: nums)
sum += num;
int n = nums.size();
return (n * (n + 1))/ 2 - sum;
}
};
<LeetCode OJ>Missing Number【268】
原文：http://blog.csdn.net/ebowtang/article/details/50457902