和为S的两个数字（C++）

  输入一个升序数组 array 和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回任意一组即可，如果无法找出这样的数字，返回一个空数组即可。

数据范围: 0≤len(array)≤10⁵，1≤array[i]≤10⁶

输入：
[1,2,4,7,11,15],15
返回值：
[4,11]
说明：
返回[4,11]或者[11,4]都是可以的 

输入：
[1,5,11],10
返回值：
[]
说明：
不存在，返回空数组

输入：
[1,2,3,4],5
返回值：
[1,4]
说明：
返回[1,4],[4,1],[2,3],[3,2]都是可以的

输入：
[1,2,2,4],4
返回值：
[2,2]

暴力穷举，时间复杂度过大，仅供参考

class Solution {
public:
    vector FindNumbersWithSum(vector array,int sum) {
        vector res;
        if(array.size() <= 1)return res;
        int start = 0,end = 1;
        while(start != array.size() - 1)
        {
            if(array[start] + array[end] == sum)
            {
                res.push_back(array[start]);
                res.push_back(array[end]);
                break;
            }
            end++;
            if(end == array.size())
            {
                start++;
                end = start + 1;
            }
        }
        return res;
    }
};

快慢标记位，start指向头部，end指向尾部，如果指向位置两数相加大于sum，那么我们让end–，如果指向位置两数相加小于sum，我们让start++即可。

class Solution {
public:
    vector FindNumbersWithSum(vector array,int sum) {
        vector res;
        if(array.size() <= 1)return res;
        int start = 0,end = array.size()-1;
        while(start < end)
        {
            if(array[start] + array[end] < sum)
                start++;
            else if(array[start] + array[end] > sum)
                end--;
            else
            {
                res.push_back(array[start]);
                res.push_back(array[end]);
                break;
            }
        }
        return res;
    }
};

使用一个容器hash记录之前已经出现过的数字x，只要之后的数字y，存在hash[sum - y]意味着有 sum - y = x，即x + y = sum，说明x，y满足题目条件。

class Solution {
public:
    vector FindNumbersWithSum(vector array,int sum) {
        //记录之前已经出现过的数字
        unordered_map hash;
        for(int i = 0;i < array.size();i++)
        {
            auto it = hash.find(sum-array[i]);
            if(it != hash.end())
                return {array[it->second],array[i]};
            hash[array[i]] = i;
        }
        return {};
    }
};