题目

数组 nums 蕴含从 0 到 n 的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有方法在 O(n) 工夫内实现吗？

留神：本题绝对书上原题稍作改变

示例 1：

输出：[3,0,1]
输入：2
 

示例 2：

输出：[9,6,4,2,3,5,7,0,1]
输入：8

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解释

数组中蕴含 0 到 n 所有整数，但就短少了一个，所以，针对这个问题有下列办法给出：

办法 1：求和求差法

1. 先计算 0 - n 所有数之和。
2. 再计算数组中所有元素之和。
3. 做差

代码如下：
`
求和法

int n = numsSize+1;
int ret1= 0;
for(int i = 0; i<n; ++i)
{ret1 += i;//sum}

int ret2 = 0;
for(int j = 0; j<numsSize; ++j)
{ret2 +=nums[j];//sum of array
}

return ret1-ret2;

`

办法 2：位运算法

思路：应用位运算的异或运算来排除。

1. 数组中元素 0 - n 短少一个。
2. 在造一组数 0 -n。
3. 后面两组数全副异或，后果就是所求的短少的数。

代码如下：
`
// 位运算

int x = 0;
for(int i = 0;i<numsSize+1; ++i)
{x^=i;// x 先和所有数异或一次}
for(int j = 0;j<numsSize; ++j)
{x ^= nums[j];// 持续异或数组中所有元素
}

return x;

`

总结

针对此类问题，求和求差法体现了数学的思维，位运算的奇妙在于能够应用异或去除反复两次呈现的数，最初剩下的数天然就是呈现一次的数。
如若各路大神还有更好的思路，请分享。