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

第七十四题

方法一：没有用到数据是单调递增的性质

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        // 因为只要找任意一组，而且是两个数相加，所以简单
        // 遍历一遍，判断sum-当前的数是否在hash中,在则返回，不在则跳过
        map<int,int> hash;
        vector<int> retans;
        for(int i =0;i<array.size();i++)
        {
            if(hash[sum-array[i]])
            {
                retans.push_back(array[i]);
                retans.push_back(sum-array[i]);
                return retans;
            }
            else
                hash[array[i]]=1;
        }
        return retans;
    }
};

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        // 方法2：因为单调递增的，所以前面的数加起来等于sum可能性不大，所以应该后面和前面一起，从两端向中间搜索
        unordered_map<int,int> hash;
        vector<int> retans;
        for(int i =0;i<array.size()/2;i++)
        {
            if(hash[sum-array[i]])
            {
                retans.push_back(array[i]);
                retans.push_back(sum-array[i]);
                return retans;
            }
            else
                hash[array[i]]=1;
            
            if(hash[sum-array[array.size()-1-i]])
            {
                retans.push_back(array[array.size()-1-i]);
                retans.push_back(sum-array[array.size()-1-i]);
                return retans;
            }
            else
                hash[array[array.size()-1-i]]=1;
        }
        return retans;
    }
};

方法3：同方法2，但是不用map了，而是利用双指针，从两段往中间走

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        // 方法3：思想同方法2，但是不用hash了，而是用双指针，让他从两段往中间走
        
        vector<int> retans;
        // 左指针从最左向右，右指针从最右向左
        int i=0,j=array.size()-1;
        // 循环结束条件：左指针>=右指针，说明没有结果 return 空
        while(i<j)
        {
            // 当左右指针之和小于sum时，左指针右移
            if(array[i]+array[j]<sum)
                i++;
            // 当左右指针之和大有sum时，右指针左移
            else if(array[i]+array[j]>sum)
                j--;
            // 左右指针之和就是sum直接返回
            else
            {
                retans.push_back(array[i]);
                retans.push_back(array[j]);
                return retans;
            }
        }
        return retans;
    }
};