如何快速找到2个不同数组中所有元素对的总和

Question

所以最近我遇到了这个编程问题,我似乎无法使复杂性降低(我当前的代码运行在O(n ^ 2)).

基本上,我有四个不同的列表(我使用python btw)的整数,正面和负面,比如列表A,B,C,D.现在,这些列表中的每一个都有1000个整数,这些整数的范围是-25000到25000包括在内.现在,假设从每个列表中我们选择一个整数,比如a,b,c,d.我想找到这些a,b,c,d的最快方法是a + b = - (c + d).

目前,我的方法依赖于遍历a,b和c,d的每个可能组合,然后尝试查找集合中的元素(a + b)是否存在于集合中 - (c + d).当然,这是不切实际的,因为它在O(n ^ 2)时间内运行,考虑到大的列表大小(1000),更是如此.

因此,我想知道是否有人能想到更有效的方式(最好是O(n log n)或更小),如果可能的话用python编码.

如果它相当令人困惑,请道歉.如果您有任何疑问请通知我,我会尽量提供更多说明.

编辑:

这个问题是一个更大问题的一部分.更大的问题表明,如果我们有4个数字序列,每个数字最多1000个整数,比如A,B,C,D,找到a,b,c,d使得a + b + c + d = 0.

我问了上面的问题,因为a + b + c + d = 0意味着a + b = - (c + d),我认为这将导致解决问题的最快方法.如果有人能想到更快的方式,请与我分享.

提前致谢!:)

Answer 1

您的问题不在于组合元素对的时间复杂度为 O(n^2)，而在于您天真地组合两个这样的过程以最终得到 O(n^4) 算法。我假设你只需要找到 >= 1 种加起来为 0 的方法——如果需要的话，我下面给出的方法可以很容易地扩展以找到所有方法。

鉴于您接受的值范围相对较窄（-25k 到 +25k，我们分别称之为 MIN 和 MAX），您需要执行以下操作：

创建 2 个大小为 (MAX - MIN + 1) 的 int 数组：“indicesA”和“indicesB”。这甚至还不到 0.5 MB 内存，因此在现代系统上无需担心。

现在循环列表 A 和 B 的所有元素，就像您所做的那样。做类似这样的伪代码（对 python 不太熟悉，所以我不确定它是否按原样有效）：

for idxA, valA in enumerate(A):
    for idxB, valB in enumerate(B):
        indicesA[valA + valB - MIN] = idxA + 1
        indicesB[valA + valB - MIN] = idxB + 1

现在，在 B 和 C 上循环时，只需将其用作 O(1) 查找表即可：

for valC in C:
    for valD in D:
        neededVal = -(valC + valD) - MIN
        if indicesA[neededVal] > 0:
            print('Found solution: {0} {1} {2} {3}'.format(A[indicesA[neededVal] - 1], 
                 B[indicesB[neededVal] - 1], valC, valD))

• 使用 0 初始化查找表：O(MAX - MIN)（~50k，在本例中小于 n^2）
• 通过循环 A 和 B 来填充查找表：O(n^2)
• 循环 C 和 D 并检查是否有解决方案：O(n^2)

总的来说，O(n^2 + (MAX - MIN)) =~ O(n^2) 给定的值。可能没有比这更好的了。