2

这是我被要求解决的一个面试问题：给定一个未排序的数组，找出 2 个数字及其在数组中的总和。（也就是说，在数组中找到三个数字，其中一个是另外两个的总和。）请注意，我已经看到了关于在给定总和 (int k) 时找到 2 个数字的问题。但是，这个问题希望您找出数组中的数字和总和。是否可以在 O(n)、O(log n) 或 O(nlogn) 中求解

有一个标准的解决方案是遍历每个整数，然后对其进行二进制搜索。有更好的解决方案吗？

public static void findNumsAndSum(int[] l) {
    // sort the array
    if (l == null || l.length < 2) {
        return;
    }
    BinarySearch bs = new BinarySearch();
    for (int i = 0; i < l.length; i++) {
        for (int j = 1; j < l.length; j++) {
            int sum = l[i] + l[j];
            if (l[l.length - 1] < sum) {
                continue;
            }
            if (bs.binarySearch(l, sum, j + 1, l.length)) {
                System.out.println("Found the sum: " + l[i] + "+" + l[j]
                        + "=" + sum);
            }
        }
    }
}
4

2 回答 2

4

这与标准问题非常相似，3SUM右侧的许多相关问题都与该问题有关。

您的解决方案是O(n^2 lg n)；有一些基于对数组进行排序的O(n^2)算法，这些算法对这个变体进行了轻微的修改。最有名的下限是（因为你可以用它来执行比较排序，如果你很聪明的话）。如果你能找到一个二次算法或更严格的下限，你会从中得到一些出版物。:)O(n lg n)

请注意，如果您愿意将整数限制在范围内，则可以使用快速傅里叶变换[-u, u]及时解决该a + b + c = 0问题。不过，如何调整它以适应问题对我来说并不是很明显。O(n + u lg u)a + b = c

于 2012-07-29T01:01:49.480 回答
2

您可以按以下方式解决它O(nlog(n))：

按升序对数组进行排序O(nlog(n))。您需要 2 个指向数组左/右端的索引。让我们称它们为iand j，i分别是左边的和j右边的。

现在计算 的总和array[i] + array[j]。

  • 如果这个和大于k，则减j一。
  • 如果这个和小于k。增加i一。

重复直到总和等于k。

因此，使用此算法，您可以找到解决方案，O(nlog(n))并且实现起来非常简单

对不起。看来我没有仔细阅读您的帖子；）

于 2012-08-02T23:31:28.813 回答