Find All Duplicates in an Array

题目来源
找出数组中所有重复元素，我用了哈希的思想，但是用数组本身来记录，代码如下：

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

可以AC，不过其实还是用了额外的空间，时间复杂度应该是O(n)的呀，但是不知道为啥跑的那么慢。
看了大神们的做法，从前往后遍历一遍，把nums[i]对应位置的数变为负数，假如已经是负数了，说明重复了，push进去。
这种做法可以很方便的获得原nums，只要取下绝对值就可以。
代码如下：

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