假设我们有三个长度n的数组，其中包含long类型的任意数。然后给我们一个数字m（同一类型），我们的任务是从每个数组中选取三个数字a，b和c，一个（换句话说，a应该从第一个数组中选取，b应该从第二个数组中选取，c应该从第三个数组中选取），所以a+b+c=m。
问：我们能选择所有三个数字，并最终得到O（n2）的时间复杂度吗？
说明：
数组是：
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（n2）时间内完成。
首先让我们解决一个简单的问题：给定两个数组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。
排序后查找对的过程需要O（N）。
现在让我们来看看最初的问题。我们现在有了第三个数组，称之为j。
所以现在的算法是：
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
外部循环运行
C次，对于每次运行，我们执行O（N）操作，使整个算法为O（N2）。