四数之和问题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上执行,总是返回空
我调试了下,condidate.size都是小于4的,所以这句里面根本就不会执行,所以一直返回空
老师能帮我看下,我这个算法写的哪里有问题?
下面是我参考的算法的地址: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
加油!:)
00
相似问题