lc hot 100之：找到所有数组中消失的数字

这题的直接思路是哈希表（又又又是哈希表哈哈哈）但是这样的话就要新建空间，不能保证o(1)的空间复杂度。

哈希表长度为n，这个数组长度也为n，所以想能不能原地修改？

因此面临的问题是：

1、如何在原数组标识已访问？

2、 如果修改了原数组，如何最后判断原值？

可以这样想：如果1-n数是满的，那么对应数组序号是0-n-1，对吧？

因此如果数num[i]存在，我们修改其对应的序号num[i]-1，即nums[(nums[i]-1)]。

修改的方式有多种，我们将其自增n，表明已访问。

最后，找到nums数组中数字仍在1-n的序号对应的数，表示这个数没有访问过，是不存在的，将他添加到结果数组里。

卡点可能在于对nums数组的想象，希望大家可以抽象的把他看成既是一个hash表，又是他本身。（有点难哈哈哈

这才是本题的精髓。

代码：

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

有一个数据报错了：

可以把+n的那一行改一下，只有没加过的数再+n，避免重复加溢出。

修改后代码：

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