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

和为S的两个数字：最直观的想法是，两层for循环，分别表示两个数，如果两个数之和等于S，则将其加入结果数组res，退出循环并返回。(超时)

    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        vector<int> res;
        bool flag=false;
        for(int i=0;i<array.size();i++)
        {
            for(int j=i+1;j<array.size();j++)
            {
                if(array[i]+array[j]==sum)
                {
                    res.push_back(array[i]);
                    res.push_back(array[j]);
                    flag=true;
                    break;
                }
            }
            if(flag)
                break;
        }
        return res;
    }

优化：使用一个uset来存储已经遍历过的数字，然后从头到尾遍历数组，如果能在uset中找到与当前元素互补S的另外一个数，则将这两个数加入结果数组中并返回，反之将当前元素加入uset中。这样就可以用空间换时间，将两层for循环降为一层for循环。

vector<int> FindNumbersWithSum(vector<int> array,int sum) 
{
    vector<int> res;
    unordered_set<int> uset;
    for(int i=0;i<array.size();i++)
    {
        if(uset.find(sum-array[i])!=uset.end())
        {
             res.push_back(array[i]);
             res.push_back(sum-array[i]);
             break;
        }
        else
             uset.emplace(array[i]);
    }
    return res;
}