五月集训——Day3：268

• • ***、题目链接
  • 一、题目
  • • 1、题目描述
    • 2、基础框架
  • 二、解题报告
  • • 1、思路分析
    • 2、时间复杂度
    • 3、代码详解
  • 三、写在最后

        Day2：Leetcod 268. 丢失的数字

        给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

        样例输入： [3,0,1]；
        样例输出： 2。

• C++给出的代码框架如下：

class Solution {
public:
    int missingNumber(vector& nums) {
    }
};

       ( 1 ) (1) (1) 排序的方法就是，用 sort 函数排序，遍历数组，找到第 i 项与 i - 1 项相差为二的中间项，并返回，或者缺少头尾。；
       ( 2 ) (2) (2) 但事实上可以使用数学思维来解决，即 应有的前 n n n项和减去现有的前 n n n项和即为丢失的那个数字。

       O ( n ) O(n) O(n) ， n n n 为数组长度；

class Solution {
public:
    int missingNumber(vector& nums) {
        int n = nums.size();
        int sum = (n * (n + 1)) / 2;
        int m = 0;
        while(n){
            n--;
            m += nums[n];
        }
        return sum - m;
    }
};

          事实上很多算法问题都是数学问题，在做题出现不知道如何下手的时候，可以看看输入与输出，找一找其中的数学规律。