四数之和问题18

来源:4-4 使用查找表的经典问题 Two Sum

向往那片天空

2018-08-31

int getSum(vector<int> condidate){
    int total;
    for(int i=0;i<condidate.size();i++)
        total+=condidate[i];
    return total;
}

void dfs(vector<vector<int>>& ret,vector<int> condidate,vector<int>& nums,int curIndex,int target){
    if(condidate.size()==4){
        int total=getSum(condidate);
        if(total==target)
            ret.push_back(vector<int>(condidate));
        return;
    }
    //cout<<condidate.size()<<endl;
    if(curIndex>nums.size()-1)
        return;
    for(int i=curIndex;i<nums.size();i++){
        if(i!=curIndex&&nums[i]==nums[i-1])
            continue;
        condidate.push_back(nums[i]);
        if(getSum(condidate)>target&&nums[i]>0){
            if(!condidate.empty())
                condidate.pop_back();
            return;
        }
        dfs(ret,condidate,nums,i+1,target);
        if(!condidate.empty())
            condidate.pop_back();
    }
}

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    sort(nums.begin(),nums.end());
    vector<vector<int>> ret;
    dfs(ret,vector<int>(),nums,0,target);
    return ret;
}

老师,这是我在网上看到的一个解决四数之和的算法,用的深度遍历的方法,用java实现的,然后我改写成了c++,但是在leetcode上执行,总是返回空http://img.mukewang.com/szimg/5b88b0f300019c0412110383.jpg

我调试了下,condidate.size都是小于4的,所以这句里面根本就不会执行,所以一直返回空http://img.mukewang.com/szimg/5b88b13c0001535d04170104.jpg

老师能帮我看下,我这个算法写的哪里有问题?

下面是我参考的算法的地址:https://blog.csdn.net/lm2009200/article/details/76184086

写回答

1回答

liuyubobobo

2018-08-31

这么小的测试用例,只有6个数字,自己调试一下,看看为什么condidate.size一直小于4?你遇到的这个问题,我怀疑直接使用4个数字的测试用例都能再现。仔细调试一下试试看?:)debug可是程序员的基本功哦,而且对于编写算法的深入理解,就在debug的过程中,进步就发生在这里哦:)


如果需要可以参考我的这个问题的参考代码:https://github.com/liuyubobobo/Play-Leetcode/tree/master/0018-4Sum/cpp-0018


加油!:)

0
0

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7410 学习 · 1150 问题

查看课程