LeetCode Notes: Find All Duplicates in an Array
Tags: javascript, programming, algorithms
Published: 2022-03-12 05:01:43


## 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:**

```js
/**
 * @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:**

```js
/**
  * @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;

};
```


Check more LeetCode Notes:<https://lwebapp.com/en/tag/leetcode>
## Reference
- [LeetCode Notes: Find All Duplicates in an Array](https://lwebapp.com/en/post/leetcode-find-all-duplicates-in-an-array)
- [442. Find All Duplicates in an Array](https://leetcode.com/problems/find-all-duplicates-in-an-array/)