版权声明：转载请联系本人，感谢配合！本站地址：http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50768898
翻译
给定一个包含从0,1,2...,n中取出来的互不相同的数字，从数组中找出一个丢失的数字。
例如，
给定nums = [0, 1, 3]
返回2。
备注:
你的算法应该运行在线性时间复杂度下。你可以只用常量空间复杂度来实现它吗？原文
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?分析
因为数组可以是非常非常大，其大小并不固定，所以哈希表应该是没用了。
中间省略了一大段的思考过程，并且先去做了下面这道题，回到这道题的时候忽然有了思路。
LeetCode 319 Bulb Switcher（灯泡切换）（从规律中发现算法……）
比如说，从零到32146的数组中，丢失的数字是4687。
我们可以计算出从0到32146的所有数字的总和是：
expectedSum：516666585我们还可以计算出从0到32146并丢掉4687的所有数字的总和是：
actualSum：516661898对，没错，就是这样……
代码如下：
代码
int missingNumber(vector<int>& nums) {
int expectedSum = 0, actualSum = 0;
for (int i = 1; i <= nums.size(); ++i) {
expectedSum += i;
}
for (int i = 0; i < nums.size(); ++i) {
actualSum += nums[i];
}
return expectedSum - actualSum;
}
