algorithm - 两对数相同的数

Question

给定一个[a_1 a_2 ... a_n]（不一定是不同的）整数列表，确定是否存在成对不同的索引w,x,y,z，例如a_w + a_x = a_y + a_z.

我知道一种方法是使用 4 级for循环，每级循环遍历一个索引。当我们得到相等的和时，检查所有索引是否成对不同。如果是，则返回true。如果我们已经用尽了所有可能性，请返回false。这有运行时间O(n^4)。

我们能做得更好吗？

Answer 1

计算 的所有可能值a_w + a_x，将它们插入哈希表。将 (a_w + a_x, w) 和 (a_w + a_x, x) 插入到第二个哈希表。

在将值插入第一个哈希表之前，检查它是否已经在表中。如果是这样，请检查第二张表。如果存在 (a_w + a_x, w) 或 (a_w + a_x, x) 中的任何一个，请不要插入任何内容（我们有一个重复的元素）。如果这两对都不在第二张表中，我们就会得到肯定的答案。

如果在处理所有 (w, x) 对之后，我们没有得到肯定的答案，这意味着不存在这样的成对不同的索引。

时间复杂度为 O(n ² )。空间要求也是 O(n ² )。

可以在 O(n) 空间中执行相同的操作，但在 O(n ² * log(n)) 时间中使用此答案的稍微修改的算法：Sum-subset with a fixed subset size：

1. 对列表进行排序。
2. 对元素使用优先级队列，包含a_w + a_x键和w, x值。用元素预先填充此队列n-1，其中 x = 0 和 w = 1 .. n-1。
3. (sum, w, x)反复从该队列中弹出最小元素并将元素放入(a_w + a_x_plus_1, w, x+1)队列（但当 x >= w 时不要放入元素）。当从队列中删除的两个连续元素具有相同的总和时停止。
4. 要处理重复项，可以比较两个连续元素的 w、x，它们的总和相等。但是使用 krjampani 的预处理思想更容易。如果排序列表包含两对重复项或单个元素重复 4 次，则成功。否则重复的值不会超过一个；在列表中只保留它的单个实例，并将其加倍值与一对“特殊”索引一起添加到优先级队列中：（2a，-1，-1）。

Answer 2

Evgeny 的解决方案可以通过如下预处理原始数组来简化。

我们首先使用哈希表来计算原始数组中每个元素的频率。如果至少有 2 个元素有重复项（它们的频率至少为 2），或者如果一个元素以至少 4 的频率出现，则答案是true。否则，如果元素a以 2 或 3 的频率出现，我们添加2a到第二个哈希表，并用a原始数组中的单个副本替换 的所有副本。

然后在修改后的数组中，对于每对索引i，我们添加到第二个哈希表，如果我们在这个哈希表中找到重复条目，则返回。ji < ja_i + a_jtrue

Answer 3

如果您有 8.5GB 的内存（无符号整数更多，如果总和或索引不跨越整个整数范围，则更少），创建三个数组。首先每个可能的总和使用 1 位。它是结果的位图。其次，每个可能的总和使用 32 位。它记录索引 j。第三个使用每个可能的总和 1 位。它是一个位域，用于记录当前迭代中是否遇到了该和 - 每次迭代都将其归零。迭代 i=0...n 和 j=i+1...n。对于每个总和，查看它是否设置在第一个位域中（如果之前遇到过）。如果是，查看第二个数组中记录的索引是否匹配 i 或 j（如果旧 j 匹配新 i 或新 j）。如果不是，请检查第二个数组中的位是否已设置（如果它是在当前迭代中设置的，因此旧 i 与新 i 匹配）。如果不是，你有一个匹配！（旧的 i 永远不会匹配旧的 j 或新的 j，新的 i 永远不会匹配新的 j。）退出。否则，在所有三个数组中记录总和并继续。

尽管它使用了价值 40 美元的内存（我喜欢现在：），但这可能比使用哈希映射和装箱要快得多。对于较大的 n，甚至可能使用更少的内存。一个缺点是数据几乎永远不会在 L2 缓存中。但是尝试将 JVM 设置为使用大页面，这样至少 TLB 未命中也不会进入主内存。处理为 o(n^2)，内存为 o(1)。