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

// 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;

};
``````