题目

数组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;

`

总结

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