剑指offer之和为定值的两个数

剑指offer之和为定值的两个数2015-10-02题目描述：

输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

输入：

每个测试案例包括两行：

第一行包含一个整数n和k，n表示数组中的元素个数，k表示两数之和。其中1 <= n <= 10^6，k为int

第二行包含n个整数，每个数组均为int类型。

输出：

对应每个测试案例，输出两个数，小的先输出。如果找不到，则输出“-1 -1”

样例输入：

6 151 2 4 7 11 15

样例输出：

4 11

思路：

最直接的做法是暴力法，两个for循环，时间复杂度为O（n*n），但是这样没有充分利用升序数组这一前提。我们假设数组为A，长度为len，给定的和为sum，最好的方法是先用数组的第一个数A[low]和最后一个数A[high]相加，看是否等于sum，如果等于sum，则找到了一组数，返回true，如果大于sum，则将较大的数向前移动一位，即high--，此时变成了第一个和倒数第二个数相加，如果小于sum，则将较小的数向后移动一位，即low++，此时变成了第二个和最后一个数相加，依此类推，如果low==high时还未找到和为sum的一组数，则返回false。该算法的时间复杂度为O（n），空间复杂度为O（1）。

针对该方法需要给出一些证明，证明如下：

对于一个升序数列A1,A2,...Ak k>=3，如果A1+Ak大于sum，那么考察k-1个数对和A1+Ak,A2+Ak,...Ak-1+Ak有sum<A1+Ak<=A2+Ak<=,...<=Ak-1+Ak，也就是说，Ak与数列中其它任何数的和都不可能等于sum，因此抛弃Ak这个数，对结果没有影响。A1+Ak如果小于sum的话，同理抛弃A1这个数对结果没有影响。

该方法对任意的整数数组都适合，另外，要输出乘积最小的一组，没必要将所有的结果保存起来，我们由下面我们高中时非常熟悉的数学公式可以证明最左边和最右边的两个符合要求的数的乘积最小。

当a+b = c时，ab<=（a+b）的平方/4，当且仅当a==b时，ab取得最大值，二者相差越远，乘积越小。