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

和为S的两个数字

https://www.nowcoder.com/practice/390da4f7a00f44bea7c2f3d19491311b

#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;
    }
};

全部评论

相关推荐

CARLJOSEPH...:宝宝你戾气太大了
点赞 评论 收藏
分享
小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享
机械打工仔:我来告诉你原因,是因为sobb有在线简历,有些HR为了快会直接先看在线简历,初步感觉不合适就不会找你要详细的了
投了多少份简历才上岸
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务