algorithm - 从给定的数字数组中找到总和值为 N 的 3 组中的所有数字

Question

给定一个数字数组:

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.

是否可以通过其他一些方法进一步改进？

Answer 1

你当然可以在 O(n^2) 中做到:对于每个 i在数组中，测试其他两个值的总和是否为 N-i .

你可以在O(n)中测试排序数组中的两个值总和是否为 k一次从两端扫过。如果您所在的两个元素的总和太大，请减小“从右到左”索引以使其变小。如果总和太小，请增加“从左到右”索引以使其变大。如果有一对有效，你会找到它们，你最多执行 2*n在一端或另一端跑出道路之前的迭代。您可能需要代码来忽略您使用的值 i , 取决于规则是什么。

您可以改用某种动态规划，从 N 向下计算，你可能会得到类似 O(n*N) 的时间或者。实际上，我不认为那更好:看起来你所有的数字都是非负的，所以如果 n比 N 大得多然后在开始之前，您可以快速丢弃数组中的任何大值，以及超过每个值 3 个副本的任何重复项(或 2 个副本，只要您在丢弃 3*i == N 的第三个副本之前检查是否 i ) .在那一步之后，n是O(N) .