假设我们有 三个 长度为 N的 数组，其中包含任意数量的type long。然后给我们一个数字 M （相同类型），我们的任务是从每个数组中选择三个数字 A ， B 和 C （换句话说 ， 应该 从第一个数组中选择 A ，从第二个数组中选择 B ，从第三个数组中选择 C。 ），以使之和 A + B + C = M 。
long
问题： 我们可以选择所有三个数字并得出 _O（N 2）的_时间复杂度吗？
插图：
数组是：
1) 6 5 8 3 9 2 2) 1 9 0 4 6 4 3) 7 8 1 5 4 3
而 中号 ，我们已经给出是 19 。那么我们的选择是从第一开始为 8 ，从第二开始为 4 ，从第三开始为 7 。
这可以在O（1）空间和O（N 2）时间中完成。
首先让我们解决一个简单的问题： 给定两个数组，A并B从每个数组中选取一个元素，以使它们的总和等于给定的number K。
A
B
K
对两个采用O（NlogN）的数组进行排序。 取指针i，j使其i指向数组的开始A并j指向的结尾B。 找到总和A[i] + B[j]并与之比较K
i
j
A[i] + B[j]
A[i] + B[j] == K
A[i]
B[j]
A[i] + B[j] < K
A[i] + B[j] > K
排序后查找对的过程为O（N）。
现在让我们来解决原始问题。现在我们有了第三个数组C。
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 2）。
N
