面试问题：三个数组和O(N*N)。

Question

假设我们有三个长度为N的任意long类型数字数组。现在给出一个同样类型的数字M，我们需要从每个数组中选出一个数字A、B和C，使得它们的和等于M。也就是说，A应该从第一个数组中选择，B从第二个数组中选择，C从第三个数组中选择。

问题：我们是否可以选择所有三个数字并且时间复杂度为O(N^2)？

Illustration:

数组如下：

1) 6 5 8 3 9 2
2) 1 9 0 4 6 4
3) 7 8 1 5 4 3

我们已经给出的 M 是 19。 那么我们的选择将是第一个中取 8，第二个中取 4，第三个中取 7。

- Keynslug

---

一份工作职位是“C++程序员”，事实上就是这样。 - Keynslug

Answer 1

这可以在O(1)空间和O(N²)时间内完成。

首先让我们解决一个简单的问题：
给定两个数组 A 和 B，从中选择一个元素，使它们的和等于给定的数字 K。

对两个数组进行排序，这需要 O(NlogN) 的时间。
取指针 i 和 j，其中 i 指向数组 A 的开头，j 指向数组 B 的结尾。
找到和 A[i] + B[j]，并将其与 K 进行比较。

• 如果 A[i] + B[j] == K，那么我们已经找到了一对 A[i] 和 B[j]
• 如果 A[i] + B[j] < K，则需要增加和，因此将 i 加一。
• 如果 A[i] + B[j] > K，则需要减小和，因此将 j 减一。

在排序后查找配对的过程需要 O(N) 的时间。

现在让我们来看看原始问题。我们现在有了第三个数组，称其为 C。

因此算法现在是：

foreach element x in C
  find a pair A[i], B[j] from A and B such that A[i] + B[j] = K - x
end for

外层循环运行 N 次，每次运行我们执行一个 O(N) 的操作，使整个算法的时间复杂度为 O(N²)。

- codaddict

---

优秀的回答，推理和解释得非常清楚。 :) - Chris

关于你将i和j向彼此靠近的部分：我记得这是正确的，但你需要解释一下原因，因为在这个过程中有一些元素对没有被检查到，比如，如果你在开始时将i增加两次，然后将j减少两次，则元素对(initial_i + 1, initial_j - 1)永远不会被检查到。一个（充分但不必要的）方法是证明任何被跳过的元素对都不可能相加为K。 - j_random_hacker

在第一轮迭代中，如果A[i] + B[j] < K，这意味着我们需要增加其中一个数字，但由于B已经排序且j是B中的最后一个元素，即B中的最大数字，因此唯一可能的方法是将i增加以尝试下一个更大的数字。--如果A[i] + B[j] > K，这意味着我们需要减少其中一个数字，但由于A已经排序且i是A中的第一个元素，即从A中可能得到的最小值，因此唯一可能的方法是将j减少以尝试下一个更小的数字。--继续归纳。 - chakrit

@chakrit：但这种推理只适用于第一步。一旦我们有A[i] + B[j] < K，其中j 不是 B 的最后一个元素，我们就有了两个选项：要么像以前一样增加i，要么增加j。（对于A[i] + B[j] > K的情况也是如此。） - j_random_hacker

我要-1直到这个算法的正确性得到证明。就像我说的，我相信它是正确的，但我想看到它被证明！ - j_random_hacker

Answer 2

您可以将其简化为两个数组的相似问题，这是一个有点出名且具有简单的O(n)解决方案的问题（涉及从两端迭代）。

1. 对所有数组进行排序。
2. 从第一个数组中尝试每个数字A一次。
3. 查找最后两个数组是否可以给我们数字B和C，使得B + C = M - A。

步骤2和3相乘给出了O(n^2)的复杂度。

- Nikita Rybak

---

不需要对第一个数组进行排序，否则就是完美的解决方案。 - Ben Voigt

@codaddict 很好的解释，顺便说一句！我花了10分钟搜索任何其他具有该问题的问题进行链接，但没有运气。 - Nikita Rybak

@Ben Aaarg，谁在乎呢，这只是nlogn :) 但你当然是对的：代码中不需要这样做。 - Nikita Rybak

Answer 3

其他解决方案已经更好了，但这是我的O(n^2)时间复杂度和O(n)内存解决方案。

将数组C的所有元素插入到哈希表中。(时间复杂度为O(n)，空间复杂度为O(n)) 取出所有(a,b)对，其中a来自A，b来自B(时间复杂度为O(n^2))。 对于每个(a,b)对，检查M-(a+b)是否存在于哈希表中(每次查询期望的复杂度为O(1))。

因此，总时间复杂度为O(n^2)，哈希表的空间复杂度为O(n)。

- MAK

---

你是不是想检查哈希表中是否存在M-a-b？ - Keynslug

@Keynslug：是的。谢谢你指出来，我已经更正了我的答案。 - MAK

Answer 4

1. 将所有的(i,j)对中A[i]*B[j]的结果存储在另一个数组D中，使用哈希数据结构进行组织。此步骤的复杂度为O(N*N)。

construct a hash named D
for i = 1 to n
    for j = 1 to n
        insert A[i]*B[j] into D

2. 对于数组C中的每个C[i]，查找是否存在于D中的M-C[i]。这一步骤的复杂度为O(N)。

for i = 1 to n
    check if M - C[i] is in D

- cnhk

---

我想你的意思是A[i]+B[j]，而不是A[i]*B[j]。但非常聪明！ - Tyler

Answer 5

对最后一个列表进行哈希。在该特定列表上执行此操作的时间复杂度为O(N)，但这将添加到下一阶段。

下一阶段是创建第一行和第二行总和的“矩阵”。然后在哈希表中查找它们匹配的数字是否存在。创建矩阵的时间复杂度为O(N*N)，而在哈希表中查找的时间复杂度为常数级别。

- CashCow

Answer 6

我有一个方案。将其中一个列表的所有元素插入到哈希表中，这样不会花费O(n)的时间。

完成后，您可以从剩余的两个数组中找出所有对，并查看它们的总和是否存在于哈希表中。

由于哈希连接是常数时间，因此总共需要平方时间。

使用这种方法，您可以节省排序时间。

另一个想法是，如果您知道每个元素的最大大小，则可以使用变体桶排序，在nlogn时间内完成。

- user483085

Answer 7

对三个数组进行排序。然后初始化三个索引

1. i 指向 A 的第一个元素，
2. j 指向 B 的最后一个元素，

3. k 指向 C 的第一个元素。 当 i、j、k 在各自的数组 A、B、C 的限制范围内时

4. 如果 A[i]+B[j]+C[k] == M，则返回

5. 如果 A[i]+B[j]+C[k] < M。如果 A[i]<=C[k] 则增加 i，否则增加 k。

6. 如果 A[i]+B[j]+C[k] > M。减少 j。

应该在 O(n) 时间内运行。

- Prahlad

Answer 8

我有另一种时间复杂度为O(N^2)，额外空间复杂度为O(N)的解决方案。

首先，对三个数组进行排序，这一步是O(N*log(N))。然后，对于A中的每个元素，创建两个数组V = Ai + B和W = Ai + C（其中Ai是当前元素）。Ai + B表示新数组V中每个元素都是B中该位置的元素加上Ai（即A中的当前元素）。W = Ai + C类似。

现在，将V和W合并，就像归并排序一样。由于两者都已排序，因此这是O(N)的。在这个具有2*N个元素的新数组中，搜索M + Ai（因为Ai被使用了两次）。可以使用二分查找在O(log n)内完成。

因此，总复杂度为O(N^2)。

- kolistivra

Answer 9

以O(N^2)的空间代价，但仍使用O(N^2)的时间，可以处理四个数组，通过计算前两个数组的所有可能和以及后两个数组的所有可能余数，对列表进行排序（由于它们都是'long'类型，其位数与N无关，因此可以在线性时间内完成），然后查看是否存在任何一组和等于任何一组余数。

- supercat

---

你可以在O(N^2)的时间和空间中哈希残差（或和），然后在O(N^2)的时间内查找所有和（或残差）。 - Neil

我的观点是，如果要对NxN数组元素的交叉连接执行某些操作，至少从O()的角度来看，可以执行两个交叉连接。不过你提到哈希让我想到了什么：基于低位进行分区怎么样？如果我们将大小为n的列表分成k=2^b个基于b个低位的分区，那么对于从任意两个列表中取出的一对分区，只需要查找第三个分区中的单个分区即可。 - supercat

是的，我理解了双重交叉连接，这也是为什么我给你点赞的原因，但我想建议哈希可能比排序更优越。就我个人而言，我暂时看不出多个哈希的意义所在。 - Neil

Answer 10

对于所有3个数组，排序并使用二分查找似乎是更好的方法。一旦数组排序完成，应该绝对采用二分查找而不是线性查找，因为后者需要n而不是log(n)。

哈希表也是一个可行的选择。

哈希和排序的组合可以降低时间复杂度，但代价是O(N平方)的空间复杂度。

- Eugene