# LeetCode Solution, Medium, 442. Find All Duplicates in an Array

# [442. Find All Duplicates in an Array](https://leetcode.com/problems/find-all-duplicates-in-an-array/)

### 題目敘述

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 <= 10**5`
-   `1 <= nums[i] <= n`
-   Each element in `nums` appears **once** or **twice**.

#### 題目翻譯

提供一個整數的陣列 `nums`，集中包含有 `n` 個元素。每個整數的元素會出現 1 或 2 次。要出出現過 2 次的元素並回傳

### 解法解析

這題特別要求讓 Time complexity 在 `O(n)`。個人覺得這題應該只有 Easy 才對，不知道為什麼分配到 Medium，可能因為有要求 Time complexity 吧。
最基本的解法就是使用一個 Set 或是 Array，紀錄已經出現過的元素。

#### 程式範例

##### Python

```python
class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        seen = set()
        return [x for x in nums if x in seen or seen.add(x)]
```

##### JavaScript

```javascript
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDuplicates = function (nums) {
    const result = [];

    for (let i = 0; i < nums.length; i++) {
        const cur = Math.abs(nums[i]);

        if (nums[cur - 1] < 0) {
            result.push(cur);
        }

        nums[cur - 1] *= -1;
    }

    return result;
};
```

##### Go

```go
func findDuplicates(a []int) []int {
	ans := make([]int, 0)
	for _, currentNumber := range a {
		rightIndex := abs(currentNumber) - 1
		if a[rightIndex] < 0 {
			ans = append(ans, rightIndex+1)
		} else {
			a[rightIndex] *= -1
		}
	}
	return ans
}

func abs(a int) int {
	if a < 0 {
		return a * -1
	}
	return a
}
```

##### Swift

```swift
class Solution {
    func findDuplicates(_ nums: [Int]) -> [Int] {
        var frequencyArr = Array(repeating: 0, count: nums.count)
        var result = [Int]()
        for num in nums {
            frequencyArr[num - 1] = frequencyArr[num - 1] + 1
            if frequencyArr[num - 1] == 2 {
                result.append(num)
            }
        }
        return result
    }
}
```

##### Kotlin

```kotlin
class Solution {
    fun findDuplicates(nums: IntArray): List<Int> {
        val seen = mutableSetOf<Int>()
        val result = mutableListOf<Int>()

        for (number in nums) {
            if (seen.contains(number)) {
                result.add(number)
            } else {
                seen.add(number)
            }
        }

        return result
    }
}
```