42.和为S的两个数字.md

42.和为S的两个数字

题目描述

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

输出描述

对应每个测试案例，输出两个数，小的先输出。

 

解题思路

下面的思路来自《剑指offer》，在《41.和为S的连续正数序列》中已经介绍过解法。

• 最容易想到的复杂度为$O(n^2)$的算法为，首先固定一个数，然后把剩下的所有数字和它相加。但这种方法效率太低了，因此想到另外一种方法，由于数组是排序的，因此可以设置两个指针，分别指向数组的头(small)和尾(big)，当两个指针指向数字之和小于S的时候，将small指针向后移动，如果两个数字之和大于S的话就把big指针向前移动，最终一定能找到这对数字，复杂度为$O(n)$。

• 外层的两个数的乘积更小，证明如下：

  假设a,b是内层的两个数，且b>a, a+b=S，同时存在外层的两个数(a-m)+(b+m)=S, m>0，那么就有(a-m)*(b+m)=ab-(b-a)*m-m^2<ab，因此外层的乘积比内层小，输出外层的两个数即可。

  也可以这样证明，假设a,b是外层的两个数，且b>a, a+b=S，同时存在内层的两个数(a+m)+(b-m)=S, m>0，那么就有(a+m)*(b-m)=ab+(b-a)*m-m^2，由于数组是递增的，因此b-a>m，所以(a+m)*(b-m)>ab，因此内层的乘积更大。

 

代码

• C++

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        vector<int> result;
        int length = array.size();
        if(length<2) return result;
        
        int pSmall = 0, pBig = length-1;
        while(pSmall < pBig){
            int curSum = array[pSmall] + array[pBig];
            if(curSum > sum) pBig--;
            else if(curSum < sum) pSmall++;
            else{
                result.push_back(array[pSmall]);
                result.push_back(array[pBig]);
                break;
            }
        }
        return result;
    }
};