相关疑难解决方法(0)

我的一个朋友最近得到了这个面试问题,这在我们看来是可以解决的,但不是在面试官认为应该可能的渐近时间范围内.这是问题所在:

你有一个N整数数组xs,排序但可能不同.您的目标是找到四个数组索引⁽¹⁾ (a,b,c,d),以便以下两个属性成立:

xs[a] + xs[b] + xs[c] = xs[d]

a < b < c < d

Run Code Online (Sandbox Code Playgroud)

目标是在O(N ²)时间内完成此操作.

首先,O(N ³ log(N))解决方案是显而易见的:对于每个(a,b,c)有序三元组,使用二进制搜索来查看是否d可以找到合适的.现在,如何做得更好？

面试官的一个有趣建议是将第一个条件重写为:

xs[a] + xs[b] = xs[d] - xs[c]

在此之后还不清楚该怎么做,但也许我们可以选择一些枢轴值P,并搜索一(a,b)对加起来为P,一(d,c)对减去它.对于给定的P,通过从数组的两端向内搜索,该搜索很容易在O(n)时间内完成.然而,在我看来,这个问题是N ²这样的值P,而不仅仅是N,所以我们实际上根本没有减小问题的大小:我们正在进行O(N)工作, O(N ²)次.

我们发现在其他地方在线讨论了一些相关的问题:在N ²时间内,在一个数组中找到添加到给定总和的3个数字是可解的,但要求总和提前修复; 适应相同的算法,但迭代每个可能的总和使我们一如既往地在N ³.

另一个相关的问题似乎是在数组中查找所有三元组,其总和小于或等于给定的总和,但我不确定这里有多少相关的东西:不等式而不是平等混合了很多东西,当然,目标是固定的而不是变化的.

那么,我们缺少什么？考虑到性能要求,问题毕竟是不可能的吗？还是有一个我们无法发现的聪明算法？

(1)实际上提出的问题是找到所有这样的(a,b,c,d)元组,并返回有多少元组的计数.但我认为即使在所需的时间限制内找到其中一个也很难.