算法 - 找出数组中两个数之和的最大数

Question

描述:

给定一个由 n 个正整数组成的数组，找到使 C=A+B 的最大 C。 A,B,C 都在给定的数组中。

示例:

1 1 1 4 5 5 6 6 10 9 C=10

1 3 6 C=-1,表示最大的C不存在

我正在寻找一种小于 O(n^3) 的算法，谁能给我一些指导？

Answer 1

对列表进行排序。从最大到最小遍历 C，从最小到 C 的值遍历 B。到目前为止，它是 O(n^2)。对于每个 (C, B) 对，计算 A，您只需要查找它是否在数组中即可。您可以对 O(n^2 log n) 的总时间使用二进制搜索。