> For the complete documentation index, see [llms.txt](https://rachel2011.gitbook.io/leetcode_cc150/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://rachel2011.gitbook.io/leetcode_cc150/leetcode/find-all-duplicates-in-an-array.md).

# Find All Duplicates in an Array

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]
```

## 题目大意：

给定一个整数数组，1 <= a\[i] <= n (n = 数组长度)，某些元素出现两次，某些出现一次。寻找数组中所有出现两次的元素。你可以不使用额外空间并且在O(n)运行时间内完成题目吗？

## 解题思路：

### 方法1 hashmap

```
class Solution(object):
    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        hashmap=collections.Counter(nums)
        return [i for i in hashmap if hashmap[i]>1]
```

### 方法2 正负号标记法

when find a number i, flip the number at position i-1 to negative. if the number at position i-1 is already negative, i is the number that occurs twice.class

```
    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        result =[]
        for num in nums:
            if nums[abs(num)-1] > 0:
                nums[abs(num)-1] = -nums[abs(num)-1]
            else:
                result.append(abs(num))
        return result
```