题目描述

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 ... n 中没有出现在序列中的那个数。

样例

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

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

提示

• 你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现？

算法

(基础数学) $O(n)$

1. 直接对数组中的数字求和，然后用 $\frac{n(n + 1)}{2} - sum$ 即可得到答案。

时间复杂度

• 只有一次求和，故时间复杂度为 $O(n)$。

空间复杂度

• 只使用了若干额外的变量，故空间复杂度为 $O(1)$。

C++ 代码

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        long long sum = 0;
        int n = nums.size();
        for (auto x : nums)
            sum += x;
        return (int)((long long)(n) * (n + 1) / 2 - sum);
    }
};