两对数字相同的总和 [英] Two pairs of numbers with same sum

问题描述

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

Given a list [a_1 a_2 ... a_n] of (not necessarily distinct) integers, determine whether there exist pairwise distinct indices w,x,y,z such that a_w + a_x = a_y + a_z.

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

I know that one way is to use 4 levels of for loops, each one iterating over one of the indices. When we get equal sums, check whether all the indices are pairwise distinct. If they are, return true. If we've exhausted all the possibilities, return false. This has running time O(n^4).

我们可以做得更好吗？

推荐答案

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

Compute all possible values for a_w + a_x, insert them to hash table. Insert (a_w + a_x, w) and (a_w + a_x, x) to second hash table.

在将值插入第一个哈希表之前，检查它是否是已经在桌子上了。如果是，请检查第二个表格。如果（a_w + a_x，w）或（a_w + a_x，x）中的任何一个存在，请不要插入任何内容（我们有一个重复的元素）。如果这些对中都没有在第二个表中，我们得到了肯定的答案。

Prior to inserting a value to first hash table, check if it is already in the table. If so, check second table. If either of (a_w + a_x, w) or (a_w + a_x, x) is there, don't insert anything (we've got a duplicate element). If neither of these pairs is in the second table, we've got positive answer.

如果在处理完所有（w，x）对后，我们没有肯定的答案，这意味着没有这种成对的不同指数。

If, after processing all (w, x) pairs, we've got no positive answer, this means there is no such pairwise distinct indices.

时间复杂度为O（n ² ）。空间要求也是O（n ² ）。

Time complexity is O(n²). Space requirements are also O(n²).

在O（n）空间中也可以这样做但是O（n < sup> 2 * log（n））时间，从这个答案略微修改算法：具有固定子集大小的Sum-subset ：

It is possible to do the same in O(n) space but O(n² * log(n)) time with slightly modified algorithm from this answer: 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次，则成功。否则不会重复单个值;只保留列表中的单个实例，并将其doubled值与特殊索引对一起添加到优先级队列中：（2a，-1，-1）。

1. Sort the list.
2. Use a priority queue for elements, containing a_w + a_x as a key and w, x as values. Pre-fill this queue with n-1 elements, where x = 0 and w = 1 .. n-1.
3. Repeatedly pop minimal element (sum, w, x) from this queue and put element (a_w + a_x_plus_1, w, x+1) to the queue (but don't put elements when x >= w). Stop when two consecutive elements, removed from queue, have the same sum.
4. To handle duplicates, it is possible to compare w, x of two consecutive elements, having equal sum. But it's easier to use krjampani's idea of pre-processing. If sorted list contains two pairs of duplicates or a single element is duplicated 4 times, success. Otherwise no more than a single value is duplicated; leave only single instance of it in the list and add its doubled value into priority queue along with a "special" pair of indexes: (2a, -1, -1).

这篇关于两对数字相同的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！