首页 > 代码库 > Leetcode#18 4Sum
Leetcode#18 4Sum
原题地址
标准DFS+剪枝。
将数字提前排序，一来方便去重，二来创造剪枝条件。
1. 如果当前数字过大，就算加上最小的数字最后都超过target，停止继续尝试之后的数字，因为后面的数字更大
2. 如果当前数字过小，就算加上后面最大的数字最后都不到target，不用再考虑这个数字了，继续尝试后面更大的数字
3. 如果当前数字之前用过了，就直接跳过不再用了（去重）
其他一些小优化：
寻找最后一个数字的时候可以二分查找
代码：
1 vector<vector<int> > res; 2 3 void dfs(vector<int> &num, vector<int> &ans, int pos, int left, int target) { 4 if (left == 0) { 5 if (target == 0) 6 res.push_back(ans); 7 return; 8 } 9 10 if (left == 1) {11 if (binary_search(num.begin() + pos, num.end(), target)) {12 ans.push_back(target);13 res.push_back(ans);14 ans.pop_back();15 }16 return;17 }18 19 set<int> record;20 for (int i = pos; i < num.size(); i++) {21 // 如果数字出现过，换后面的数字考虑22 if (record.find(num[i]) != record.end())23 continue;24 // 如果数字过大，肯定爆掉，跳出循环25 if (num[i] * left > target)26 break;27 // 如果数字太小，肯定够不着target，考虑后面更大的数字28 if (num[num.size() - 1] * (left - 1) < target - num[i])29 continue;30 record.insert(num[i]);31 ans.push_back(num[i]);32 dfs(num, ans, i + 1, left - 1, target - num[i]);33 ans.pop_back();34 }35 }36 37 vector<vector<int> > fourSum(vector<int> &num, int target) {38 vector<int> ans;39 sort(num.begin(), num.end());40 dfs(num, ans, 0, 4, target);41 return res;42 }
Leetcode#18 4Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。