今天带来一道找到数组中所有消失的数字，这道题直接的做法就是循环两次，一次统计所有出现的，一次把没出现的输出，很简单，但是空间复杂度有点高。

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> vec(nums.size() + 1);
        vector<int> as;
        for (int i = 0; i < nums.size(); i++) {
            vec[nums[i]]++;
        }
        for (int i = 1; i <= nums.size(); i++) {
            if (vec[i] == 0) {
                as.push_back(i);
            }
        }
        return as;
    }
};

那么有没有不使用额外空间的方法呢，那就是要对原数组做文章。我们可以对原数组进行标记，我们已知有一个含 n 个整数的数组 nums，其中 nums[i] 在区间 [1, n] 内，那么我们可以把每一位看做一个数。我们访问一个数，便把这个数对应的数值的那一位变成一个负数。那么这样以来等访问完数组的每一位，对应数值的那一位的数便全都变成负数了。我们只需要再访问一次数组，那么不是负数的那几位便是消失的数字，把他们输出就可以了。代码如下：

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            nums[abs(nums[i]) - 1] = -abs(nums[abs(nums[i]) - 1]);
        }
        vector<int> vec;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > 0) {
                vec.push_back(i + 1);
            }
        }
        return vec;
    }
};