题解 | #和为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;
    }
};

全部评论

相关推荐

醉蟀:你不干有的是人干
点赞 评论 收藏
分享
06-20 17:42
东华大学 Java
凉风落木楚山秋:要是在2015,你这简历还可以月入十万,可惜现在是2025,已经跟不上版本了
我的简历长这样
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-08 10:39
一个证都没&nbsp;我能填什么
程序员小白条:别人有,你为什么没有,还是这个道理,社会就是比较,竞争,淘汰,你要安逸,那么就要做好淘汰的准备
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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