我的一个朋友最近遇到了这个面试问题,我们觉得这个问题可以解决,但是不能在面试官认为可能的渐进时间界内完成。问题如下:
(1)你有一个包含
N
个整数的数组xs
,已排序但可能不唯一。你的目标是找到四个数组下标(a,b,c,d)
,使得满足以下两个条件:
xs[a] + xs[b] + xs[c] = xs[d]
a < b < c < d
目标是以O(N2)的时间复杂度完成此操作。
首先,一个O(N3log(N))的解决方案很显然:对于每个(a,b,c)有序三元组,使用二分查找来确定是否可以找到一个合适的d。现在,如何做得更好呢?
面试官提出的一个有趣的建议是将第一个条件重写为:
xs[a] + xs[b] = xs[d] - xs[c]
目前不清楚如何继续,但或许我们可以选择一个枢轴值P,并搜索加起来为P的(a,b)
对和减去它的(d,c)
对。对于给定的P,在数组两端向内搜索在O(n)时间内容易实现。然而,问题在于存在N2个这样的值P,而不仅仅是N个,因此实际上并没有减少问题的规模:我们正在进行O(N)次O(N2)工作。
我们发现其他地方在线讨论了一些相关问题:查找数组中加起来等于给定值的三个数字可以在N2时间内解决,但需要提前确定总和;通过迭代每个可能的总和来调整相同算法始终保持在N3。
另一个相关问题似乎是在数组中查找所有三元组之和小于或等于给定和,但我不确定那里的内容有多少相关性:一个不等式而不是一个等式会使事情变得复杂,当然,目标是固定的而不是变化的。
那么,我们缺少什么?考虑到性能要求,该问题是否不可能?还是有一个聪明的算法我们无法发现?
(1) 实际上,所提出的问题是查找所有这样的(a,b,c,d)
元组,并返回它们的数量。但我认为在所需的时间限制内找到一个也已经够难了。