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

Question

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

基本上，我有四个不同的整数列表(顺便说一句，我使用的是 python)，包括正数和负数，比如列表 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) 具有给定的值。可能没有比这更好的了。