前言

最近，刚刚起步数据结构，浅浅了解了所谓的空间复杂度与时间复杂度，什么最好情况，最坏情况，平均情况，还以为时间复杂度就是计算时间，空间复杂度就是在计算内存。最后才了解到

时间复杂度不计算时间，计算大概的运算次数

空间复杂度不计算空间，计算大概定义的变量个数

实际上，刚接触到数据结构感觉很枯燥且很难，而且现阶段感觉有点迷茫，希望大家可以给些建议。今天，记录自己第一次在leetcode平台上答题，意义非凡，迈出了勇敢的第一步。由于本人目前只学c语言，其他语言暂未学习，因此用c语言小试牛刀一下，本人水平有限，请多担待。

好了，直接进入我们的主题：打开leetcode，看到我们这一道题。这里第一次接触leetcode有点不适应。

数组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/problems/missing-number-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

?看到这里，有什么想法没有，大家先自己看看，有什么想法没有。

我这里想出了两种解法：

第一种解法：异或

相异为1，相同为0（这是解题核心），刚开始这种思路是想不到的，不过题目练多了，这种思路很快就会成为你解决这种问题的第一方法。

这道题中，有一个小细节，那就是比如numsSize=10，就是10个值，但是实际上本来0到10有11个值，具体想清楚一点，就是缺少了一个嘛。想通了这点，这道题就变得非常简单了，先遍历一遍数组，现在我们不知道却哪一个，定义一个未知数int x = 0，因为0跟任何数异或都是任何数。先让数组内的所有数都异或到x上去，相当于x跟数组所有值异或了，唯独没有跟未知数x异或，然后我们在让x异或全部的数（指地是加上x的所有数），想清楚这个问题，最后return x即可。看看我们的代码。实际上，这道题很简单。

int missingNumber(int* nums, int numsSize){
    int x  = 0;
    for(size_t i = 0;i<numsSize;i++)
    {
        x^=nums[i];
    }
    for(size_t i = 0;i<=numsSize;i++)
    {
        x^=i;
    }
    return x;
}

解法二：等差数列求解法

这个解法思路更加简单明了，这就是实际上总数组的和减去本身数组的和最后得出我们究竟消失了哪个数。即最后返回totalsum-sum。

int missingNumber(int* nums, int numsSize){
    int totalsum = (numsSize)*(numsSize+1)/2;
    int sum = 0;
    for(int i =0;i<numsSize;i++)
    {
        sum+=nums[i];
    }
    return totalsum-sum;
}

本次就到这里结束了，谢谢大家的支持与关注。