题目来源
这道题应该算是做过很多次了吧，基本上每次面试都得问一下。
然后刚刚写代码还是写了一会才写出来。
主要思想就是把相应的位置放上相应的数值。其实相当于利用原有空间来做哈希。

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        auto n = nums.size();
        vector<int> res;
        for (auto i=0; i<n; i++) {
            if (nums[i] != i+1 && nums[nums[i]-1] != nums[i]) {
                swap(nums[i], nums[nums[i]-1]);
                i--;
            }
        }
        for (auto i=0; i<n; i++)
            if (nums[i] != i+1)
                res.push_back(i+1);
        return res;
    }
};

我以为这样已经是最好的方法了，没想到还能稍微优化一下。
完全只要遍历两遍，一点都不多。
就是第一次遍历的时候把每个位置里对应数值的位置改为负数。
然后第二遍判断哪些是正数就是消失的数。
代码如下：

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