四数之和问题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
相似问题