面试题：三个数组，O(N*N)

假设我们有three长度数组N其中包含任意数量的类型long。然后我们得到一个数字M（相同类型）我们的任务是选择三个数字A, B and C每个数组中的一个（换句话说A should从第一个数组中选取，B从第二个开始和C从第三个）所以总和A + B + C = M.

Question: could we pick all three numbers and end up with time complexity of O(N²)?

插图：

数组是：

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

And M我们得到的是19。 那么我们的选择就是8从一开始，4从第二个和7从第三。

This can be done in O(1) space and O(N²) time.

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

对两个数组进行排序需要 O(NlogN)。
求指点i and j以便i指向数组的开头A and j指向末尾B.
求总和A[i] + B[j]并将其与K

• if A[i] + B[j] == K我们发现 这对A[i] and B[j]
• if A[i] + B[j] < K， 我们需要 增加总和，因此增加i.
• if 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

The outer loop runs N times and for each run we do a O(N) operation making the entire algorithm O(N²).