leetcode算法：FindAllDuplicatesinanArray

Given an array of integers, 1 ≤ a[i] ≤ n (n &＃61; 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]


这道题描述的是&＃xff1a;
给我们一个 长度为n 的列表&＃xff0c;里面全都是整数 并且满足每个整数都是1到n之间的数

我们要做的是&＃xff1a; 找到里面出现两次的整数

要求我们 使用O(n) 的时间复杂度和 O(1)的空间复杂度


描述一下思想&＃xff1a;
　　这道题困扰了我很久&＃xff0c;在网上查阅了一些代码&＃xff0c;用了一些时间才搞懂。
　　O(n) 的时间复杂度 只允许一次遍历&＃xff0c;就找到出现2次的元素
　　O(1) 的空间复杂度&＃xff0c;我们不能开辟线性空间。
　　
　　参考了网上大神的代码&＃xff0c;他的想法是&＃xff0c;把原本给我们的数组&＃xff0c;当作hash来做散列映射。具体的做法是这样&＃xff1a;
　　对一个数组 A &＃61; [X,X,X,X,X,X]
　　　　从头开始遍历&＃xff0c;对每个元素 i &＃xff1a;
　　　　　　如果 A[ 绝对值(i)-1 ] >0: 我们就让 A[ 绝对值(i)-1 ] &＃61; -A[ 绝对值(i)-1 ]
　　　　　　如果 A[ 绝对值(i)-1 ] <0: 绝对值(i)就是第二次出现&＃xff0c;我们把它追加到结果列表
　　　　返回 结果列表

　　为什么这样就行呢&＃xff1a;
　　　　1 列表长度是n&＃xff0c;并且没个元素都是 1到n之间的数&＃xff0c;所以 任何一个元素i &＃xff0c;用 绝对值(i) - 1 作下标&＃xff0c;不会越界
　　　　2 初始情况下&＃xff0c;数组每个元素都是正数(1到n之间) , 我们遍历数组&＃xff1a;
　　　　　　每当第一次拿到一个数i&＃xff0c;把 A[绝对值(i)-1] 该为负数,(i这个数值第一次出现&＃xff0c;响应位置上的数字一定是正数&＃xff0c;我们把他改成了负数)
　　　　　　如果我们拿到一个数i&＃xff0c;这个数值是第二次出现&＃xff0c;我们在取 A[绝对值(i)-1] 的时候&＃xff0c;之前我们就把他改为负数了&＃xff0c;所以&＃xff0c; 绝对值(i) 这个数&＃xff0c;这一次取到 一定是重复的。
　　　　　　　　把这个重复的数放到结果列表里
　　　　3 为什么 我们把里面的数字 取相反数&＃xff0c;不做其他标记呢&＃xff1f; 因为里面数字取相反数 我们还能用绝对值找到原来的数。这里每一个数在我们做映射算法的时候&＃xff0c;会依据这个数找到一个数组的位置&＃xff0c;所以不能用其他标记。
　　　　　　

我的python代码&＃xff1a;