我在一次面试中被问到这个问题。
给定一个int数组，找出其和小于某个数字的所有三元组
在一番混乱之后，我告诉采访者，最好的解决方案仍然会导致最坏的运行时O（n3），并且可能需要O（n3）。
面试官公然不同意我的观点，并告诉我"你需要回到你的算法……"。
我是不是错过了什么
可能的优化是：
- 删除数组中大于
sum的所有元素 - 对数组进行排序
- 运行
O(N^2)以获取a[i] + a[j]，然后在[j + 1, N]的范围内对sum - a[i] - a[j]进行二进制搜索，索引是可能的候选数，但应该减去j，因为它们已经被覆盖
复杂性将是O(N^2 log N)，稍微好一点。
您可以解决此O(n^2)时间：
- 首先，对数组进行排序
- 然后，使用第一个指针
i在数组上循环 - 现在，使用第二个指针
j从那里向上循环，同时使用第三个指针k从结尾向下循环 - 每当你处于
A[i]+A[j]+A[k] < X的情况下，你就会知道所有j<k'<k都是一样的，所以用k-j和j递增你的计数。我保留了隐藏不变量A[i]+A[j]+A[k+1] >= X，所以增加j只会使该语句更强 - 否则，递减
k。当j和k相遇时，递增i - 你只会增加
j和减少k，所以他们需要O(n)的摊销时间来满足
在伪代码中：
count= 0
for i = 0; i < N; i++
j = i+1
k = N-1
while j < k
if A[i] + A[j] + A[k] < X
count += k-j
j++
else
k--
我看到你要求所有三元组。很明显，可能会有O(n^3)三重态，所以如果你想要它们，你需要同样多的时间，最坏的情况是。
这是一个输出大小很重要的问题的例子。例如，如果数组只包含1, 2, 3, 4, 5, ..., n，并且最大值设置为3n，那么每个三元组都将是一个答案，并且必须进行Ω（n3）运算才能将它们全部列出。另一方面，如果最大值是0，那么在确认所有项目都太大后，最好在O(n)时间内完成。
基本上，我们想要一个运行时间类似于O(f(n) + t)的输出敏感算法，其中t是输出大小，n是输入大小。
O（n2+t）算法的工作原理是基本上跟踪三元组从超过极限过渡到低于极限的过渡点。然后它会产生表面下的一切。空间是三维的，所以表面是二维的，你可以在总的恒定时间内沿着它逐点追踪。
以下是一些python代码（未经测试！）：
def findTripletsBelow(items, limit):
surfaceCoords = []
s = sorted(items)
for i in range(len(s)):
k = len(s)-1
for j in range(i, len(s))
while k >= 0 and s[i]+s[j]+s[k] > limit:
k -= 1
if k < 0: break
surfaceCoords.append((i,j,k))
results = []
for (i,j,k) in surfaceCoords:
for k2 in range(k+1):
results.append((s[i], s[j], s[k2]))
return results
O（n2）算法。
- 对列表进行排序
- 对于每个元素ai，这就是计算组合数量的方法：
- 二进制搜索并找到最大aj，使得j<i和ai+aj<=总计
- 二进制搜索并找到最大ak，使得k<j和ai+aj+ak<=合计
对于（ai，aj）的这个特定组合，k是小于或等于总和的和的数目。
现在尽可能减少j并增加k（但ai+aj+ak<=合计）
增量和递减的总数小于i。因此，对于特定的i，复杂性为O（i）。因此总的复杂度是O（n2）。
我省略了许多角落条件，但这应该会给你一个想法。
编辑：
在最坏的情况下，存在O（n3）解。因此，明确地输出它们肯定需要O（n3）时间。没有办法绕过它。
但是，如果您想返回一个隐式列表（即组合的压缩列表），这仍然有效。压缩输出的一个例子是1:p中k的（ai，aj，ak）。