四数之和 疯狂减枝 leetcode 18

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。 注意： 答案中不可以包含重复的四元组。 示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

class Solution { public: int book[1000]={0}; vector<vector<int>> answer; vector<int> path; int size; void dfs(vector<int>& nums, int count,int target,int num,int index){ if(count ==4&&num == target){ answer.push_back(path); return; } //if(num>=target) return ; for(int i=index;i<size;i++){ //if(!path.empty()&&nums[i] == path.back()) if(i>index&&nums[i]==nums[i-1]) continue; if(size-i<4-path.size()) continue; if(i<size-1&&num + nums[i]+(int)(3-path.size())*nums[i+1]>target) continue; if(i<size-1&&num+nums[i]+(int)(3-path.size())*nums[size-1]<target) continue; path.push_back(nums[i]); book[i]=1; dfs(nums,count+1,target,num+nums[i],i+1); path.pop_back(); book[i]=0; } } vector<vector<int>> fourSum(vector<int>& nums, int target) { sort(nums.begin(),nums.end()); size = nums.size(); dfs(nums,0,target,0,0); return answer; } };

知识点

可以通过减枝来弥补算法的先天不足，我的dfs的速度比起标答的三重循环要慢很多但是可以通过神奇的减枝技巧，排序后减枝效果很棒。我注意到 删掉 (int) 后，无法过，原来 vector.size() 返回一个无符号数，而若后面乘上负数后会变成一个很大的数，而不是负数，所以需要强制转换成int 类型。