题解 | #和为S的两个数字#

题目难度：中等
题目考察：双指针，hash
题目内容：输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回两个数的乘积最小的，如果无法找出这样的数字，返回一个空数组即可。
题目分析：
这种题有很多种做法下面给出两个常见做法
算法1（hash）
a+b=sum，要找到a*b最小值，sum是已知的，可以枚举a，判断有没有b，怎么判断有没有b？，总不能再枚举一遍吧，明显不需要，用hash存起来就行，思路很简单，但是要考虑很多细节，下面给出代码

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        int ans=1e9;
        vector<int>a;
        unordered_map<int,int>hash;    
           //hash表
        for(int i=0;i<array.size();i++)
            hash[array[i]]++;
            //array[i]出现次数加1
        for(int i=0;i<array.size()&&array[i]<sum/2;i++)
        {
            //枚举a
            if(hash.count(sum-array[i]))
            {
                //b出现过
               if(ans>array[i]*(sum-array[i]))
               {//新的答案更小则更新
                   ans=array[i]*(sum-array[i]);
                   a.clear();
                   a.push_back(array[i]);
                   a.push_back(sum-array[i]);
               }
            }
        }
        //这时特判ab相等时时候，需要有两个a
        if(hash[sum/2]>=2)
        {
            if(ans>sum*sum/4)
               {
                   a.clear();
                   a.push_back(sum/2);
                   a.push_back(sum/2);
               }
        }
        return a;
    }
};

复杂度分析
枚举第一个数 时间复杂度 O(n)
hash表处理每个数 空间复杂度 O(n)
题目说了给的数组是有序的，这种解法并没有用到这个性质，说明并不是最优解，下面来进行优化
算法2（二分）
a+b=sum,枚举a，b可以二分，复杂度O(nlogn)
不过时间复杂度高了，不细说了
算法3(双指针)
上图说话



很明显这是利用了单调性，右端点向右 和增大，左端点向右和减小
下面给出代码

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        int ans=1e9;
        vector<int>a;
        for(int i=0,j=array.size()-1;i<array.size()&&i<j;i++)
        {
            while(j>=1&&array[i]+array[j]>sum)
            {
                j--;
            }
            if(array[i]+array[j]==sum)
            {
                if(array[i]*array[j]<ans)
                {
                    ans=array[i]*array[j];
                    a.clear();
                    a.push_back(array[i]);
                    a.push_back(array[j]);
                }
            }
        }
        return a;
    }
};

复杂度分析
左右端点从1移动到n并且不会回退 时间复杂度 O(2*n)
没有额外空间 空间复杂度 O(1)