我碰到了这篇文章，其中报告了以下面试问题：
给定两个数字数组，找出两个数组中的每个数组是否具有相同的整数集？建议一种算法，它可以比NlogN更快地运行而又没有额外的空间？
我能想到的最好的是：
（a）对每个数组进行排序，然后（b）沿两个数组移动两个指针，并检查是否找到不同的值…但是步骤（a）已经具有NlogN复杂性了：(
（a）扫描最短数组并将值放入映射，然后（b）扫描第二个数组并检查是否找到了不在映射中的值…这里我们具有线性复杂度，但是我们使用了额外的空间
…所以，我想不出这个问题的解决方案。
有想法吗？
感谢您的所有答案。我觉得其中许多是正确的，但我决定选择ruslik的，因为它提供了我没有想到的有趣选项。
您可以通过选择用于累积的交换函数（例如加法或XOR）和参数化哈希函数来尝试概率方法。
unsigned addition(unsigned a, unsigned b); unsigned hash(int n, int h_type); unsigned hash_set(int* a, int num, int h_type){ unsigned rez = 0; for (int i = 0; i < num; i++) rez = addition(rez, hash(a[i], h_type)); return rez; };
这样，在您确定误报概率将低于某个阈值之前的尝试次数将不取决于元素的数量，因此它将是线性的。
编辑 ：通常情况下，集合相同的概率很小，因此可以使用带有多个哈希函数的O（n）检查进行预过滤：尽可能快地确定它们是否肯定不同或是否存在概率它们是否相等，以及是否应使用慢速确定性方法。最终的平均复杂度将为O（n），但最坏的情况将是确定性方法的复杂度。
