在数组中找到两个数字，它们的和最大且这个和也是数组中的一个元素。

Question

我最近在一次面试中遇到了这个问题：

给定一个数组，找到两个数的和最大，且这个和也是数组中的一个元素。

输入：6 10 12 34 41 16 输出：16

[更新]我的代码如下：

    public class Solution {
    public static int findMaximumNumbers(int a[])
    {
        Set<Integer> set=new HashSet<>();
        for(int n:a) set.add(n);
        Arrays.sort(a);
        int max=Integer.MIN_VALUE;
        for(int i=a.length-1;i>0;i--)
        {
            for(int j=i;j>=0;j--)
            {
                int sum = a[i] + a[j];
                if(set.contains(sum) && max<sum)
                   max=sum;
            }
        }
        return max;
    }

    public static void main(String[] args) {
        System.out.println( findMaximumNumbers(new int[]{ 6, 10, 12, 34, 40, 16, 41, 47, 74 }));
        System.out.println( findMaximumNumbers(new int[]{ 2, 25, 35, 40, 42, 60 }));
    }
}

这个算法的时间复杂度为O(n^2)。有没有更好的算法？

- NewUser

---

“j=i” 是正确的吗？假设20也在列表中，你能做到10 + 10 = 20吗？ - Andreas

从复杂度的角度来看，你需要执行n * (n-1) / 2次加法（如果这两个元素不必是不同的，则需要执行n^2次）。我认为你无法做得比O（n^2）更好。另外请注意：不要写成int a[]，而应该写成int[] a（方括号影响类型，因此应该写在类型旁边，而不是变量名旁边）。 - Turing85

FYI: 如果你将方法改为使用 varargs findMaximumNumbers(int... a)，那么你就不需要创建数组 findMaximumNumbers(6, 10, 12, 34, 41, 16)。 - Andreas

假设你的列表中有值为40、47和74...你的算法将会在求出41+6=47之后，返回没有找到40+34=74。如果对列表进行排序，则无需检查最后一个条目，因为任何总和都将大于列表中的任何元素。 - mavriksc

你的代码不起作用。对于输入 2, 25, 35, 40, 42, 60，它返回了 42（2 + 40），而正确答案是 60（25+35）。 - Andreas

Answer 1

这是我能想到的最快方法。由于列表已排序，您可以向后工作，尝试查找是否有任何一对数加起来等于数组中剩余的最大值（在i循环中）。它将尽可能快地短路，得出正确答案。在j循环中，当您达到小于目标值一半的值时停止计数（没有用迭代不能加起来达到目标值的剩余值）。但我希望有人能做得更好。原始代码将执行n*(n-1)/2次迭代，但即使没有解决方案，这个方法也总是会做得更少。

public static int findMaximumNumbers(int a[])
{
    Set<Integer> set=new HashSet<>();
    for(int n:a) set.add(n);
    Arrays.sort(a);
    if (a[0] == 0)
        return a[a.length-1];
    for(int i=a.length-1;i>0;i--)
    {
        int j = i-1;
        int m = a[i] / 2;
        while (j >= 0 && a[j] > m) {
            if (set.contains(a[i]-a[j]))
                return a[i];
            j--;
        }
    }
    return -1;
}

- Ian Mc

---

当输入为0 1时，这将失败。 - Kaushal Kumar Singh

已纠正。谢谢。 （我假设只有正数）。问题没有说明。 - Ian Mc

如果输入是0、1、2、3和10，输出必须为3，但你的代码将会输出10。 - Kaushal Kumar Singh

我不明白问题。任意两个元素都是[0,10]。 - Ian Mc

如果只涉及正数，那么它应该能正常工作。但是对于负数的情况，比如-2 0，结果应该是-2而不是-1。 - Kaushal Kumar Singh

同意。如果输入应允许负数，我会修改答案。 - Ian Mc

Answer 2

如果您的数字是在1到M范围内的整数，那么您可以通过以下步骤以O(Mlog(M))的时间复杂度完成：

1. 计算值的直方图 2. 使用快速傅里叶变换执行卷积 3. 搜索卷积中存在的最大值

示例Python代码：

import scipy.signal
import time

def hist(X):
    """Prepare a histogram of X"""
    h = [0]*(max(X)+1)
    for x in X:
        h[x] += 1
    return h

A = [6, 10, 12, 34, 41, 16]
H = hist(A)
R = scipy.signal.fftconvolve(H,H)
for x in sorted(A,reverse=True):
    if R[x] > 0.5:
        print x
        break
else:
    print 'No solutions'

关键在于直方图的卷积是所有元素可能和的直方图。

当然，如果您有100个值在1到10 ** 100范围内的数字，则这比您的O（n ^ 2）算法效率低，因此仅在值受限时才有用。

- Peter de Rivaz

Answer 3

如果你先对数组进行排序，那么你可以按升序逐对检查，将两个相邻的数字相加并检查它是否包含在数组中。

int myArray[];

Arrays.sort(myArray);

int a = -1, b, highest = Integer.MIN_VALUE;
for(int i = 0; i < myArray.length - 1; i++) 
{
    int sum = myArray[i] + myArray[i + 1];

    int startCheck = i + 1;
    while(myArray[startCheck] < sum && startCheck < myArray.length)
        startCheck++;

    if(myArray[startCheck] == sum && sum > highest)
    {
        a = i;
        b = i + 1;
        highest = sum;
    }
}

// Found 2 elements whose sum is on the array
if(a != -1)
{

}

- Nadir