LeetCode 442 数组中重复的数据[哈希表] HERODING的LeetCode之路

解题思路：
第一种方法是最耗费时间空间的方法，哈希表法，用哈希表存储数字的个数，最后返回个数为2的结果，代码如下：

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        unordered_map<int, int> mp;
        for(auto& num : nums) {
            mp[num] ++;
        }
        vector<int> res;
        for(auto& [a, b] : mp) {
            if(b == 2) {
                res.emplace_back(a);
            }
        }
        return res;
    }
};

但是上述方法显然是不满足常数额外空间的要求的，也没利用上长度为n，范围为[1,n]的条件，既然题中给定了这些条件，那么不如将每个位置i的值num与位置num-1对应，将出现一次，就将num-1位置标记为负数，表明出现了一个，只要再次出现判断对应位置是否为负即可，代码如下：

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        for(int i = 0; i < nums.size(); i ++) {
            int num = abs(nums[i]);
            if(nums[num - 1] > 0) {
                nums[num - 1] *= -1;
            } else {
                res.emplace_back(num);
            }
        }
        return res;
    }
};