# Find All Duplicates in an Array

## Description

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]
```

## Solution

Idea: mark the existence of a number `num` by negating `nums[num - 1]`.

```cpp
class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> ans;
        for(int i = 0; i < nums.size(); ++i){
            int idx = abs(nums[i]) - 1;
            if(nums[idx] < 0)
                ans.push_back(idx + 1);
            else
                nums[idx] = -nums[idx];
        }
        // restore the array if the array cannot be changed when the function returns
        /*
        for(int &num : nums){
            if(num < 0)
                num = -num;
        }
        */
        return ans;
    }
};
```
