如何快速找到两个不同阵列中所有元素对的总和

所以最近我遇到了这个编程问题，我似乎无法使复杂度降低（我当前的代码在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），我认为这会导致解决问题的最快方法。如果有人能想到更快的方式，请与我分享。

在此先感谢！ :)

来源

2017-02-23 Russell Ng

您是否在寻找适用于该条件的所有组合？对， – Whud

是的，就是这样。可以肯定的是，至少会有一个这样的组合。 –

在最坏的情况下，当C = -A和D = -B时，你将得到Θ（n^2）解，所以你的算法需要至少n^2个步骤来产生输出。 – Bolo

你的问题不是结合成对的元素是O（n^2），而是事实上，你结合两个这样的过程天真地结束了一个O（n^4）算法。我假设你只需要找到> = 1的方法加起来为0 - 如果需要，我的方法可以很容易地扩展到找到全部的方式。

既然你已经接受值的范围相对较窄（-25k至+ 25K，让我们叫那些MIN和MAX分别），这里就是你要做的：

创建大小为（2个INT数组最大值 - 最小值+ 1），“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

现在只需循环就当以此为O（1）查找表B和C：

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在这种情况下更小）
通过循环上的填充查找表和B：O（n^2）
循环在C和D和che （n^2）

总的来说，O（n^2 +（MAX - MIN））=〜O（n^2）与给定的值。可能做不到比这更好。

来源

2017-04-04 01:35:10 tohoho

如何快速找到两个不同阵列中所有元素对的总和

回答

相关问题