两对数字相同的总和

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）。