algorithm - 如何在未排序的数组中找到 2 个数字及其总和

Question

这是我被要求解决的一个面试问题:给定一个未排序的数组，找出数组中的 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);
            }
        }
    }
}

Answer 1

这与标准问题非常相似3SUM ，右边的许多相关问题都是关于这个的。

您的解决方案是O(n^2 lg n)；有 O(n^2) 算法 based on sorting the array , 对此变体稍作修改即可使用。最著名的下限是 O(n lg n)(因为您可以使用它来执行比较排序，如果您很聪明的话)。如果您能找到次二次算法或更严格的下限，您将从中获得一些出版物。 :)

请注意，如果您愿意将整数限制在 [-u, u] 范围内，则有一个解决方案是 a + b + c = 0 问题 O(n + u lg u) 使用 Fast Fourier Transform .不过，如何针对 a + b = c 问题调整它对我来说并不是很明显。