给定的是一个数字数组：
1, 2, 8, 6, 9, 0, 4
我们需要找到三个一组中的所有数字，它们的总和为 N（在本例中为 11）。在这里，三人一组的可能数字是：
{1,2,8}, {1,4,6}, {0,2,9}
我能想到的第一个解决方案是 O(n^3)。后来我可以用这种方法改进一点（n^2 log n）：
1. Sort the array.
2. Select any two number and perform binary search for the third element.
可以通过其他一些方法进一步改进吗？
你当然可以这样做O(n^2)：对于i数组中的每一个，测试其他两个值的总和是否为N-i。
您可以通过一次从两端扫描来测试O(n)排序数组中的两个值是否相加。k如果您所在的两个元素的总和太大，请减少“从右到左”索引以使其更小。如果总和太小，则增加“从左到右”索引以使其更大。如果有一对有效，您会找到它们，并且您最多执行2*n迭代，然后在一端或另一端用尽道路。您可能需要代码来忽略您使用的值 as i，这取决于规则是什么。
相反，您可以使用某种动态编程，从 开始向下工作N，并且您最终可能会得到类似O(n*N)左右的时间。实际上，我认为这并没有更好：看起来你所有的数字都是非负数，所以如果n比N你开始之前大得多，你可以快速从数组中抛出任何大值，以及超过 3 个副本的任何重复项每个值（或 2 个副本，只要您3*i == N在丢弃 的第 3 个副本之前检查是否i）。在这一步之后，n是O(N)。