# LC 442. Find All Duplicates in an Array

### [Problem link](https://leetcode.com/problems/find-all-duplicates-in-an-array/)

###### tags: `leedcode` `medium` `python` `c++`

Given an integer array <code>nums</code> of length <code>n</code> where all the integers of <code>nums</code> are in the range <code>[1, n]</code> 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<code>O(n)</code>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:**

- <code>n == nums.length</code>
- <code>1 <= n <= 10⁵</code>
- <code>1 <= nums[i] <= n</code>
- Each element in <code>nums</code> appears **once** or **twice** .

## Solution 1
#### Python

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        res = []
        d = defaultdict(int)

        for num in nums:
            d[num] += 1
        for num, freq in d.items():
            if freq == 2:
                res.append(num)

        return res

#### C++

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        unordered_map<int, int>umap;

        for (int num: nums) {
            umap[num]++;
        }
        for (auto it: umap) {
            if (it.second == 2) {
                res.push_back(it.first);
            }
        }
        return res;
    }
};

## Solution 2
#### Python

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        res = []
        for i in range(len(nums)):
            if nums[abs(nums[i]) - 1] < 0:
                res.append(abs(nums[i]))
            nums[abs(nums[i]) - 1] = -nums[abs(nums[i]) - 1]
        return res

#### C++

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        int idx = 0;
        for (int i = 0; i < nums.size(); i++) {
            idx = abs(nums[i]) - 1;
            if (nums[idx] < 0) {
                res.push_back(abs(nums[i]));
            }
            nums[idx] = -nums[idx];
        }
        return res;
    }
};

>### Complexity
>n = nums.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(n) |
>| Solution 2 | O(n) | O(1) |

## Note
sol2用idx變更+-的想法十分巧妙, 可以學起來.