# Missing Number【268】

Datetime:2016-08-23 01:22:05         Topic: LeetCode          Share        Original >>

### 268. Missing Number

My Submissions

Total Accepted:  31740 Total Submissions:  83547 Difficulty:  Medium

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

Hide Tags

Hide Similar Problems

```//思路首先：
//我真服了这个题，题意理解错了，我还以为是干嘛呢！
//后来才明白原来是随机从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;
}
};```