arrays - 面试题: three arrays and O(N*N)

Question

假设我们有三个 长度为N 的数组，其中包含long 类型的任意数字。然后我们得到一个数字 M(相同类型)，我们的任务是选择三个数字 A 、B 和 C 每个数组中的一个(换句话说，A 应该从第一个数组中挑选，B从第二个数组中挑选，C/strong> 来自第三个)所以总和A + B + C = M。

问题:我们能否选择所有三个数字并以 O(N²) 的时间复杂度结束？

---

插图:

数组是:

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。

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²)。