给定具有多个重复条目的arrays，重复输入O（N）时间和恒定空间
我们给出了一个大小为N的数组，其中包含0到N-2范围内的整数，包括0和N-2。
该arrays可以有多个重复的条目。 我们需要在O（N）时间和常量空间中找到一个重复的条目。
我正在考虑获取arrays中所有entires的乘积和总和，以及0到N-2范围内所有数字的乘积和总和。
然后，总和的差异和产品的划分将给出两个方程式。 如果给出只有两个重复的条目，这种方法会起作用，但由于可能有两个以上，我认为我的方法失败了。
有什么建议么？
编辑：数组是不可变的。 我意识到这是一个重要的信息，我很抱歉我忘了早些提到这一点。
这是一个很好的待遇。 在解决这个问题之前，它会通过一些简单的问题。
http://aperiodic.net/phil/archives/Geekery/find-duplicate-elements.html
它包含一个解决方案，用于何时可以修改输入数组，另一个用于何时无法修改。
链接永远死亡的简要总结：数组索引从0 … N-1运行，数组值运行0 … N-2。 因此，每个数组元素都可以被视为数组本身的索引（或“指针”）：元素i “指向”元素ra[i] ， ra[i]指向ra[ra[i]] ，依此类推。 通过反复遵循这些指针，我最终必须进入一个循环，因为如果不重新访问某个节点或其他节点，我们肯定不能永远。
现在，最后一个元素N-1没有被任何其他元素指向。 因此，如果我们从那里开始并最终进入一个循环，那么沿途的某个地方必须有一个可以从两个不同的地方到达的元素：我们第一次采取的路线，以及作为周期一部分的路线。 像这样的东西：
N-1 -> a1 -> a2 -> a3 ^ \ / v a6 <- a5 <- a4
在这种情况下，a2可以从两个不同的地方到达。
但是可以从两个不同的地方到达的节点正是我们正在寻找的节点，数组中的副本（两个不同的数组元素包含相同的值）。
那么问题是如何识别a2，答案是使用Floyd的循环寻找算法 。 特别是它告诉我们O（N）时间和O（1）空间中循环的“开始”。
假设我们被允许更改数组，当你通过数组在那个“位置”上交换每个元素时（例如，如果当前元素是curr然后用[curr]交换它）但是如果[curr]已经有然后你知道curr是重复的。
a = array... for i = 0; i < length(a); i++ curr = a[i] if a[curr] == curr: return duplicate curr swap(a[i], a[curr]) # Now a[curr] == curr and so if it happens again we know it is a duplicate.
这将是O（n）和恒定空间。
扫描数组并将每个元素添加到集合中。 如果该项目已存在于该集合中 – 您有一个骗局。
初始化一个大小为N-2的位数组，所有条目都为0.每个索引将代表0到N-2范围内的所有项目。
循环遍历您的数组并通过设置bitarray[number] == 1将项添加到您的bitarray。 如果element已包含1，那么您已经添加了元素，立即返回。
如果在没有找到重复的情况下到达数组的末尾，则返回-1。
受到这个SO问题的启发，我想我会选择首先使用维基百科中找到的O（n）（虽然不一定很快）算法就地对数组进行排序（ 这里有很好的图形排序演示），然后循环生成的数组，用于查找下一个数字等于当前数字的位置。
尝试使用其他数据结构。 某些数据结构（如HashSet）在添加或搜索时不会遍历当前元素，从而保留O（n）。
HashSet hSet = new HashSet(); for(int i = 0; i < array.length(); i++){ if(hSet.contains(array[i]) return array[i]; else hSet.add(array[i]); } return -1;
虽然我不确定这是否能满足你的记忆要求，但是extraneon之前发布的第二次遍历的post可能更符合你的要求
（抱歉还不能添加评论….）
@Blastfurnace啊..很好地抓住for循环首先需要检查
if a[i] == i: continue # Don't swap with yourself!
如果数组是不可变的，那么你可以只保留以下元素，即跳过a [i] == i然后从[i]转到a [a [i]]。 这将触及一个循环，然后我们可以使用“如何检测链表中的循环”解决方案（保持2个指针，一个以1的速度移动，另外2个，当它们都遇到你时，你知道你已经达到了循环）。
如果我们可以更改数组，然后将其保持不变，那么我们就可以作弊:)从i = 0开始，将[a [i]]变成负整数（如果它还没有），如果它已经是负数，那么我们知道元素a [i]已被访问过两次。 在返回之前将所有底片转回正面（对于0使用MIN_INT）