# LeetCode Notes: Find All Duplicates in an Array

## Question

Given an integer array `nums`

of length `n`

where all the integers of `nums`

are in the range `[1, n]`

and each integer appears **once** or **twice**, return *an array of all the integers that appears twice*.

You must write an algorithm that runs inĀ `O(n)`

Ā time and uses only constant extra space.

**Example 1:**

Input:nums = [4,3,2,7,8,2,3,1]

Output:[2,3]

**Example 2:**

Input:nums = [1,1,2]

Output:[1]

**Example 3:**

Input:nums = [1]

Output:[]

**Constraints:**

`n == nums.length`

`1 <= n <= 105`

`1 <= nums[i] <= n`

- Each element in
`nums`

appears**once**or**twice**.

## Solution One

**Analysis:**

Use the unique feature of `Set`

to continuously add the numbers in `nums`

to an empty `Set`

, and then use the `set.add`

method to determine whether there are repeated numbers by getting the length of `set`

to increase.

**Code:**

```
/**
* @param {number[]} nums
* @return {number[]}
*/
var findDuplicates = function (nums) {
const set = new Set(); // unique value test
const result = []; // result array
nums.forEach((n) => {
const preSize = set.size;
// Use the set.add method to determine whether there are duplicate numbers by getting the length of the set to increase
set.add(n);
// find duplicate numbers
if (preSize === set.size) {
result.push(n);
}
});
return result;
};
```

## Solution Two

**Analysis:**

Traverse the entire array, treat each number as the array position information, and then reverse the number corresponding to each position to a negative number, which is equivalent to making a mark, indicating that the position corresponding to this number is already occupied by a number, and we will meet again next time If this number is found to be negative, it means that it has already appeared.

For example `[4,3,2,7,8,2,3,1]`

, when reaching the first `2`

, the number `3`

whose position is `1`

is flipped to `-3`

, go By the next `2`

, the number `-3`

in position `1`

can be found, which has been flipped, indicating that the number `2`

occurs twice.

**Code:**

```
/**
* @param {number[]} nums
* @return {number[]}
*/
var findDuplicates = function(nums) {
let result = [];
for (let i = 0; i < nums.length; i++) {
let num = Math.abs(nums[i]);
if (nums[num - 1] > 0) {
/**
The purpose of flipping the number to a negative number is to make a mark to indicate that the position corresponding to the number is already occupied by a number. If the number is found to be a negative number next time, it means that it has already appeared.
For example [4,3,2,7,8,2,3,1]
When you go to the first 2, the number in position 1 is 3, flip the 3 to -3, and when you go to the next 2, when you flip 3, you find that it has been flipped.
*/
nums[num - 1] *= -1;
} else {
result.push(num);
}
}
return result;
};
```

## Comments