题解 | #和为S的两个数字# 基于“有序集合”的剪枝和查找

#include <set>
#include <vector>
class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        // 先创建一个空数组，为了应对特殊情况的返回值
        vector<int> res;
        int n = array.size();
        if(n == 0 || sum <= array[0]) return res;
        // 创建集合，通过 “集合查找” 这个方便的工具进行搜索
        set<int> se;
        for(const auto& i:array){
            se.insert(i);
        }
        for(int i=0; i<n; i++){
            // 剪枝：无论是输入还是这个集合（默认升序）都是有序的，因此可以剪枝
            if(sum <= array[i]){
                return res;
            }else{
                // 分别处理符合条件与不符合条件的情况
                if(se.find(sum-array[i]) != se.end() ){
                    res.push_back(array[i]);
                    res.push_back(sum-array[i]);
                    return res;
                }else{
                    se.erase(array[i]);
                }
            }
        }
        return res;
    }
};