问题
问题描述：给定一个整数数组，1 <= a[i] <= n，其中 n 为数组长度。有些元素出现 2 次，有些只出现 1 次，请找出所有出现 2 次的元素。
要求：在 O(n) 的时间内，并不使用额外的空间。
栗子：
输入：
[4,3,2,7,8,2,3,1]
输出：
[2,3]
想看英文的戳这里：原题地址
解题思路
如何判断出现了 2 次呢？
按常规思路，可以用额外的数组或者 map 来记录元素出现的次数，这样实现起来比较简单。比如用数组 count[] 来记录次数。
// 初始化 count[n] = 0，count 中有 n 个元素。
// 记录每个数字出现的次数
count[a[i] - 1] += 1
但是题目要求不使用额外的空间，所以只能在数组 a[] 上做文章。
同时可以借鉴常规思路的做法，在 a[i] 出现时，将其标记为已出现。由于 a[i] 全为正整数，所以我们可以想到一个比较取巧的方式，就是将 a[i] 对应位置的数标记成 对应的负数, 即 a[a[i]-1] *= -1。当再次遇到 a[i] 时，如果其对应的数已经为负数，则可判断为重复。
那么有个问题来了，如果遍历过程中遇到之前标记的负数了，怎么办？很简单，只要取 abs(a[i]) 即可。
步骤图解
- 初始状态
QQ20190410-0.png
-
遍历 4，a[3] = -7
QQ20190410-1.png 遍历 3，a[2] = -2
QQ20190410-2.png
- 遍历 2，a[1] = -3
QQ20190410-3.png
- 遍历 7，a[6] = -3
QQ20190410-4.png
- 遍历 8，a[7] = -1
QQ20190410-5.png
- 遍历 2，a[1] 已经为负数，则表示重复
QQ20190410-6.png
- 遍历 3，a[2] 已经为负数，则表示重复
QQ20190410-7.png
- 遍历 1，a[0] = -1，结束。
QQ20190410-8.png
代码实现
python 代码如下：
class Solution(object):
def findDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
res = []
// 逐个遍历，将 num 所对应的 index 设置为负数。
for num in nums:
positiveNum = abs(num)
// 已经置为负数，说明有相同的数
if nums[positiveNum-1] < 0:
res.append(positiveNum)
else:
nums[positiveNum-1] *= -1
return res
