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;

};

Check more LeetCode Notes:https://lwebapp.com/en/tag/leetcode

Reference

• LeetCode Notes: Find All Duplicates in an Array
• 442. Find All Duplicates in an Array