## 题目描述：

LeetCode 442. 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]
```

## 解题思路：

```遍历nums，记当前数字为n（取绝对值），将数字n视为下标（因为a[i]∈[1, n]）

## Python代码：

``````class Solution(object):
def findDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
ans = []
for n in nums:
if nums[abs(n) - 1] < 0:
ans.append(abs(n))
else:
nums[abs(n) - 1] *= -1
return ans
``````

```遍历nums，记当前下标为i

## Python代码：

``````class Solution(object):
def findDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
ans = []
for i in range(len(nums)):
while nums[i] and nums[i] != i + 1:
n = nums[i]
if nums[i] == nums[n - 1]:
ans.append(n)
nums[i] = 0
else:
nums[i], nums[n - 1] = nums[n - 1], nums[i]
return ans
``````

Pingbacks已关闭。