面试问题：三个数组和O（N * N）
假设我们有三个长度为N的数组，其中包含任意长度的数字。 然后我们给出一个M （相同types），我们的任务是从每个数组中select三个数字A ， B和C （换句话说， A 应该从第一个数组中挑选出来， B从第二个数组中挑选出来， C从第三个）所以总和A + B + C = M。
问题：我们可以select所有三个数字，最终的时间复杂度为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 。 那么我们的select是从第一个8 ，第二个4 ，第三个7 。
这可以在O（1）空间和O（N 2 ）时间完成。
首先让我们解决一个更简单的问题：
给定两个数组A和B从中select一个元素，使它们的和等于给定的数字K
对两个数组进行sorting（OlogN）。
以指针i和j让i指向数组A的开始， j指向B的结尾。
求和A[i] + B[j]并将其与K进行比较
- 如果
A[i] + B[j] == K我们已经find了A[i]和B[j] - 如果
A[i] + B[j] < K，我们需要增加总和，所以增加i。 - 如果
A[i] + B[j] > K，我们需要减小和，所以减lessj。
sorting后find这对的过程需要O（N）。
现在让我们把原来的问题。 我们有第三个数组，现在称之为C
所以现在的algorithm是：
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）操作，使得整个algorithmO（N 2 ）。
你可以把它减less到两个数组的类似问题，这是有名的，并有简单的O（n）解决scheme（涉及从两端迭代）。
- sorting所有数组。
- 从第一个数组中尝试每个数字
A一次。 - 查找最后两个数组是否可以给我们数字
B和C，使得B + C = M - A
步骤2和步骤3相乘给我们O（n ^ 2）的复杂性。
其他的解决scheme已经更好了，但是这里是我的O（n ^ 2）时间和O（n）内存解决scheme。
将数组C的所有元素插入散列表。 （时间复杂度O（n），空间O（n））取所有对（a，b），a来自A，b来自B（时间复杂度O（n ^ 2））。 对于每一对，检查M（a + b）是否存在于hastable中（每个查询的复杂度为O（1））。
所以，总体时间复杂度为O（n ^ 2），散列表的空间复杂度为O（n）。
哈希最后的列表。 做这个的时间是O（N）在这个特定的列表，但是这将被添加到下一个阶段。
下一个阶段是为他们的前两行创build一个“matrix”。 然后在哈希中查找它们的匹配数字是否在那里。 创buildmatrix是O（N * N），而在哈希中查找是恒定的时间。
将另一个数组D中所有对（i，j）的A [i] * B [j]存储在散列数据结构中。 这一步的复杂性是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中是否存在MC [i]。这一步的复杂度是O（N）。
for i = 1 to n check if M - C[i] is in D
我有一个解决scheme。 将列表中的所有元素插入到一个哈希表中。 这不会花费O（n）的时间。
一旦完成，你可以从剩余的2个数组中find所有的对，看它们的和是否存在于哈希表中。
因为散列连接是不变的，我们总共得到一个二次时间。
使用这种方法可以节省sorting时间。
另一个想法是，如果你知道每个元素的最大尺寸，你可以使用一个变化的桶sorting，并在nlogn时间。
以O（N ^ 2）空间为代价，但仍然使用O（N ^ 2）时间，可以通过计算前两个数组中所有可能的和，以及最后两个数组中所有可能的残基列表（可能是线性时间，因为它们都是'long'types，其位数与N无关），然后查看是否有任何和等于任何余数。
sorting所有3个数组，并使用二进制search似乎是一个更好的方法。 一旦数组sorting后，一定要进行二分search，而不是线性search，这取n而不是log（n）。
哈希表也是一个可行的select。
散列和sorting的组合可以减less时间，但是以O（N square）空间为代价。
我有另外的O(N^2)时间复杂度， O(N)额外的空间复杂性解决scheme。
首先，sorting三个数组，这一步是O(N*log(N)) 。 然后，对于A每个元素，创build两个数组V = Ai + B和W = Ai + C （ Ai是当前元素）。 Ai + B意味着这个新数组V中的每个元素都是B中的那个位置上的元素加Ai （ A的当前元素）。 W = Ai + C是相似的。
现在，合并V和W ，如合并sorting。 由于两者都是sorting的，所以这是O(N) 。 在这个有2*N元素的新arrays中，searchM + Ai （因为Ai被使用了两次）。 这可以用二进制search在O(log n)完成。
所以总的复杂度是O(N^2) 。
对三个数组进行sorting。然后初始化三个索引
- 我指着A的第一个元素，
- j指向B和B的最后一个元素
-
k指向C的第一个元素。而i，j，k在它们各自的数组A，B，C的范围内
-
如果A [i] + B [j] + C [k] == M返回
-
如果A [i] + B [j] + C [k] <M，则如果A [i] <= C [k]，则增加i，否则增加k。
- 如果A [i] + B [j] + C [k]> M，则减lessj。
哪个应该在O（n）中运行。
怎么样：
for a in A for b in B hash a*b for c in C if Kc is in hash print abc
这个想法是在A和B中散列所有可能的对。接下来，对于C中的每个元素，看看散列中是否存在剩余的zum。
