剑指offer42和为S的两个数字

剑指offer42

1、头尾双指针
时间复杂度：O(n)
空间复杂度：O(1)
一次遍历

个人代码

class Solution {
public:
    //头尾双指针
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        vector<int>v;
        if(array.size()<2||sum<array[0])
            return v;
        int low=0;
        int high=array.size()-1;
        int mul=array[high]*array[high]; //初始乘积，取一个取不到的较大值
        while(low<high)
        {
            int s=array[low]+array[high];
            if(s<sum)
                ++low;
            else if(s>sum)
                --high;
            else if(s==sum) //sum和符合
            {
                int m=array[low]*array[high];//计算乘积
                if(m<mul) //较小乘积则取代原来数据
                {
                    v.clear(); //更新元素
                    v.push_back(array[low]); 
                    v.push_back(array[high]);
                    mul=m;//更新当前存储的元素乘积
                }
                ++low; //继续遍历
                --high;
            }
        }
        return v;
    }
};

2、哈希
a+b=sum；第一次遍历元素全部存入hash,第二次遍历找sum-array[i],更适用于无序情况
时间复杂度:O(n)
空间复杂度:O(n)
两次遍历
优化:一次遍历，一遍存入hash，一遍寻找sum-array[i]
分析：
1、对于凑不成和为sum的无论怎么找都找不到，不需考虑
2、对于能凑成的对a，b有两种情况，比如a在前面，b在后面，遍历到a时，在hash表中寻找sum-a即b肯定找不到，但是遍历到b时，a已经存入hash中，能找到sum-b=a,即这个数对还是可以成功找出来，所以完全可以只遍历一次。

个人代码

 //哈希
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        vector<int>v;
        if(array.size()<2||sum<array[0])
            return v;
       unordered_map<int,int>mp;
       int mul=INT_MAX;//当前较小乘积，初始取大值
       for(int x:array)
       {
           if(mp.find(sum-x)!=mp.end()&&x*(sum-x)<mul) //找到，并且乘积小于之前，更新结果，更新乘积
           {
                   mul = x*(sum-x); //二者乘积
                   v.clear();
                   v.push_back(min(x,sum-x));
                   v.push_back(max(x,sum-x));
                   continue;
           }
           ++mp[x];  //mp的第二个参数无所谓，这里用不到
       }
        return v;
    }