我最近在一次面试中遇到了这个问题:
给定一个数组,找到两个数的和最大,且这个和也是数组中的一个元素。
输入: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)。有没有更好的算法?
n * (n-1) / 2
次加法(如果这两个元素不必是不同的,则需要执行n^2
次)。我认为你无法做得比O(n^2)更好。另外请注意:不要写成int a[]
,而应该写成int[] a
(方括号影响类型,因此应该写在类型旁边,而不是变量名旁边)。 - Turing85findMaximumNumbers(int... a)
,那么你就不需要创建数组findMaximumNumbers(6, 10, 12, 34, 41, 16)
。 - Andreas2, 25, 35, 40, 42, 60
,它返回了42
(2 + 40),而正确答案是60
(25+35)。 - Andreas