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(javascript)

/** 可以对比 448 一样的解题思路
 * @param {number[]} nums
 * @return {number[]}
 */
// const findDuplicates = function (nums) {
//   for (let i = 0; i < nums.length; i++) {
//     const index = i
//     while (nums[index] !== index + 1 && nums[index] !== nums[nums[index] - 1]) {
//       const temp = nums[index]
//       const nextIndex = nums[index] - 1
//       nums[index] = nums[nextIndex]
//       nums[nextIndex] = temp
//     }
//   }
//   return nums.reduce((acc, v, index) => {
//     if (v !== index + 1) {
//       acc.push(v)
//     }
//     return acc
//   }, [])
// }

// https://leetcode.com/problems/find-all-duplicates-in-an-array/discuss/92390/Python-O(n)-time-O(1)-space
// 另外一种思路，把数组自己当作一个 hashMap
const findDuplicates = function (nums) {
  const result = []
  for (const x of nums) {
    const index = Math.abs(x) - 1
    if (nums[index] < 0) {
      result.push(Math.abs(x))
    } else {
      nums[index] *= -1
    }
  }
  return result
}