企业网站设计期末考试百度号码认证平台官网首页

196-寻找缺失的数

给出一个包含 0 .. N 中 N 个数的序列，找出0 .. N 中没有出现在序列中的那个数。

样例

N = 4 且序列为 [0, 1, 3] 时，缺失的数为2。

挑战

在数组上原地完成，使用O(1)的额外空间和O(N)的时间。

标签

贪心

思路

在 N 个数字中，寻找在 0 .... N 中没有出现的数，只需计算数组之和与 0 + 1 + 2 + ... + N 的差即可

code

class Solution {
public:/**    * @param nums: a vector of integers* @return: an integer*/int findMissing(vector<int> &nums) {// write your code hereint size = nums.size();if (size <= 0) {return 0;}long sum1 = 0, sum2 = 0;for (int i = 0; i < size; i++) {sum1 += nums[i];sum2 += i;}sum2 += size;return sum2 - sum1;}
};