异或

基于a ^ a = 0的思想，将数组中的数和0-n异或，没丢失的数都是成对出现则抵消，这样就能找到缺失的数字。

时间复杂度$O(N)$，空间复杂度$O(1)$

AC代码

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res = 0;
        for (int i = 0 ; i < nums.size() ; i ++) {
            res ^= i ^ nums[i];
        }
        res ^= nums.size();
        return res;
    }
};

数学公式

利用等差数列求和公式，计算出如未确实数字的和，再减去数组所有数的和，则得到缺失的数字。

时间复杂度$O(N)$，空间复杂度$O(1)$

AC代码

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res = 0;
        for (int i = 0 ; i < nums.size() ; i ++) {
            res ^= i ^ nums[i];
        }
        res ^= nums.size();
        return res;
    }
};