# 442. Find All Duplicates in an Array

Given an array of integers, 1 ≤ a\[i] ≤ n (n = size of array), some elements appear **twice** and others appear **once**.

Find all the elements that appear **twice** in this array.

Could you do it without extra space and in O(n) runtime?

**Example:**\\

```
Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]
```

```cpp
vector<int> findDuplicates(vector<int>& nums) { // time: O(n); space: O(1)
    vector<int> res;
    for (int i = 0; i < nums.size(); ++i) {
        int idx = abs(nums[i]) - 1;
        if (nums[idx] < 0) {
            res.push_back(idx + 1);
        }
        nums[idx] = -nums[idx];
    }
    return res;
}
```

```cpp
vector<int> findDuplicates(vector<int>& nums) { // time: O(n); space: O(1)
    vector<int> res;
    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] != nums[nums[i] - 1]) {
            swap(nums[i], nums[nums[i] - 1]);
            --i;
        }
    }
    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] != i + 1) {
            res.push_back(nums[i]);
        }
    }
    return res;
}
```

```cpp
vector<int> findDuplicates(vector<int>& nums) { // time: O(n); space: O(1)
    vector<int> res;
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        nums[(nums[i] - 1) % n] += n; 
    }
    for (int i = 0; i < n; ++i) {
        if (nums[i] > 2 * n) res.push_back(i + 1);
    }
    return res;
}
```
