一、题目描述

原题传送门

数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
示例 1：

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

示例 2：

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

本题的题目思路很简单，就是给你一个数组，然后让你输出连续的数组中消失的那一个数字。本题我给出两种解法

二、方法1：求和相减【C语言】

1、思路分析

首先我们来看看使用求和相减法的思路是怎样的

这个思路不难想到，只需要运用一个等差数列的求和公式求和从0到n的总和，然后用这个总和值减去题目给出的数组数字的总和，无论应对哪一个案例，这个方法都是适用的

2、整体代码展示

我们来看一下代码

int missingNumber(int* nums, int numsSize){
    //1.先使用等差数列求和公式求出总的和
    int ret = (1 + numsSize) * numsSize/ 2;
    
    //2.使用循环遍历这个数组，题目给出的所有输出
    for(int i = 0;i < numsSize; ++i)
        //3.实行一个作差，找出缺少的那一个数
        ret -= nums[i];

    //4.返回的结果就是缺失的那个数字
    return ret;
}

3、代码详解

然后我们分步来讲解一下

首先第一步，使用一个等差数列的求和公式，求出从1到numSize所有数字的总和，放入变量ret中
然后第二步，使用循环遍历一下整个数组，用上面求出的ret减去题目给出的nums数组中的每一个数字
最后第三步，返回的结果即为消失的那个数组

可以看出，本思路非常简单，这个大家应该是都可以想到，接下去我们来看第二个思路

三、方法2：异或位运算【C语言】

1、思路分析

异或这种位运算，不知道大家之前在学习C语言的时候有没有注意，如果忘记了就再去看一下吧 – >异或位运算
整体的思路大概是声明一个变量，将其初始化为0，然后和题目中给出的所有数字先以后一遍，接着再用异或完的数据与0~N的数字再进行一个异或，最后变量中保存的数字便是消失的那个数字

2、整体代码展示

先看一下整体的代码

int missingNumber(int* nums, int numsSize){
    int N = numsSize;
    int x = 0;      //存储异或的数字

    //1.首先对给出的所有数字进行一个异或
    for(int i = 0;i < numsSize; ++i)
        x ^= nums[i];

    //2.再将给出的数字与完整的所有0~N的数进行一个异或
    for(int j = 0;j <= N; ++j)
        x ^= j;

    //3.两次异或后的结果即为消失数字
    return x;
}

3、代码详解

由于下面要用到异或的规则，所以先给出规则的定义

【所有数字和0异或都是它自己本身】
【所有数字和它自己异或都是0】
【异或运算具备交换律和结合律】

然后我们来分析一下这段代码以及解释一下这个异或的逻辑

在这里插入图片描述

从以上图示可以看出，首先第一步，将变量x与题目给出是所有数进行一个异或
然后第二步，再与从0~N的所有数字进行一个异或后，因为异或运算具有交换律和结合律，所以两两相同的数字异或后一定为0，最后其实只剩下8和9这两个数字，然后再和9去进行一个异或，然后9和9先异或就是0,0再和8异或就是8自己本身
最后这个x的值就是8，返回即可

如果对以上逻辑有异或，可以到编译器里自己调试一下，就可以很清楚了

四、方法3：哈希表【C++】

1、思路分析

然后最后一种思路呢，是我近阶段才看到的一种方法，觉得可不错，也分享给大家，主要是使用到高阶数据结构中的【哈希表】

整体的思路大概是将题目中给出的数字先放入哈希表中，然后再去遍历从0~n的所有数字，去哈希表中寻找是否有与其相同的数字，若是在遍历的过程中发现有数字不存在，则说明这个就是消失的那个数字，记录下这个数字跳出循环的遍历，返回这个数字即可

2、整体代码展示

然后展示一下代码

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        unordered_set<int> set;
        int n = nums.size();

        //1.首先讲题目给出的数字放入哈希表中
        for(int i = 0;i < n; ++i)
            set.insert(nums[i]);

        int missing = -1;       //消失的数字
        
        //2.然后遍历从0~n的所有数字，去哈希表中寻找是否有与其相同的数字
        for(int j = 0;j <= n; ++j)
        {
            //3.若是发现有数字没有在表中，则表明此为消失的数字
            if(!set.count(j))
            {
                //4.记录这个消失的数字
                missing = j;
                break;      //已经找到这个数字，跳出循环的遍历
            } 
        }
        return missing;
    }
};

3、代码详解

然后我们对代码来解说一下，逻辑并不复杂，一步步下来就行

首先呢我们需要去定义一个哈希集合，用来存放题目中给出的数字
接着就是将题目中给出的所有数字放入哈希集合中集合，这里使用的是一个API【insert()】
其次我们要定义一个变量用于保存那个消失的数字，然后遍历从0~n的所有数字，去哈希表中寻找是否有与其相同的数字。这里使用的是一个API【count()】，作用是统计当前的这个数字是否又在哈希表中出现过，取反【!】表示的就是没有出现的数字，若是符合，则使用missing变量去记录这个数字，然后break跳出循环，因为已经找到了和这个消失的数字就不要再寻找了
最后返回即可