如何在无序数组中找到2个数字及其总和

Question

这是我被要求回答的一个面试问题：给定一个未排序的数组，找出数组中的两个数字及其和。（也就是说，在数组中找到三个数字，其中一个是其他两个数字的和。）请注意，当求和（int k）时，我看到了关于寻找2个数字的问题。然而，这个问题要求你找出数组中的数字和和。可以用O（n）、O（logn）或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

你可以在O（nlog（n））中解决，如下所示：

在O（nlog（n））中对数组进行升序排序。需要两个指向数组左/右端的索引。我们把它们叫做i和j，i是左边的，而j是右边的。

现在计算数组[i]数组[j]的和。

• 如果该总和大于k，则将j减少一
• 如果此总和小于k。将i增加一

重复，直到总和等于k。

因此，使用该算法，您可以在O（nlog（n））中找到解决方案，而且实现起来非常简单

很抱歉看来我没有仔细阅读你的帖子；）

Answer 2

这非常类似于标准问题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问题。