再战江湖之算法问题

今天在网上看到这么一个问题："在一个整数数组中寻找符合A+B=C的组合使得C为最大，其中
A、B、C为数组三个不同的元素；如不存在符合条件的组合，请输出无解"

很久没有考虑过算法问题了，突然有兴致挑战一下自己。经过一番思考，我所能想到的最好的算法复杂度是O(N*N)。如有兄弟姐妹知道更好的解法，一定别忘了羞辱我一下。

先回到正题考虑这么一个子问题：任意给定一个整数K和一个有序数组，请判断该数组是否包含两个数A和B，使得A+B=K；如果存在，请输出A和B
这个问题可以在O(N)时间内解决，方法如下：
假设有序数组为[C1,C2,...,Cn]，且C1<=C2<=...<=Cn。考察收尾两个数有这么几种可能：
(1) C1 + Cn = K。好的，子问题解决，输出C1和Cn
(2) C1 + Cn > K。Cn和数组中任意数字的和都会不小于C1+Cn，而后者大于K。所以如果子问题有解，Cn肯定不会是A或B中的一个。换句话说，A和B如果存在，必然存在于[C1,...Cn-1]。
(3) C1 + Cn < K。类似，C1和数组中任意数字的和都会不大于C1+Cn，而后者小于K。所以如果子问题有解，C1肯定不会是A或B中的一个。换句话说，A和B如果存在，必然存在于[C2,...Cn]。
上面这个判断的复杂度是O(1)，而子问题要么已被解决，要么子问题规模减一，直至数组中只剩一个数(这意味着子问题无解)。因此，子问题的复杂度应该是O(n)。

回到原始问题，我的算法如下：
(1) 先对整个数组排序。
(2) 先考察Cn。利用前面子问题的算法我们可以在O(n)的时间内判断出[C1,...Cn-1]中是否存在A和B，使得A+B=Cn。如果子问题有解，因为Cn是数组最大数，所以原问题有解且找到，算法结束。如果子问题无解，则Cn肯定不是我们要找的C，原问题规模减一。换句话说考察Cn-1，判断[C1...Cn-2]中是否存在A和B，使得A+B=Cn-1。重复此步直至数组中只剩一个元素，这意味着原问题无解，算法结束

上面算法的第一步复杂度可以降到O(N*logN)。至于第二步，由于子问题复杂度是O(N)，而最多重复N次，所以第二步整体复杂度不会超过O(N*N)。综合考虑，此算法复杂度是O(N*N)。