四数之和
一级减枝，但是也通过
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> result; sort(nums.begin() , nums.end()); for (int i = 0; i < nums.size(); i++) { if (nums[i] > target && target>=0) return result;//减枝，当target大于0，第一个值大于target时，认为无效直接返回 for (int j = i + 1; j < nums.size(); j++) { int left = j + 1; int right = nums.size() - 1; while (left < right) { if (((long)nums[i] + nums[j] + nums[left] + nums[right]) == target)//要转换成long 要不会溢出 { if(find(result.begin() , result.end() , vector<int>{nums[i], nums[j], nums[left], nums[right]})==result.end() ) result.push_back(vector<int>{nums[i],nums[j],nums[left],nums[right]}); while (left < right && nums[left] == nums[left + 1]) left++; while (left < right && nums[right] == nums[right - 1]) right--; left++; right--; }else if((long)nums[i] + nums[j] + nums[left] + nums[right] > target) right--; else left++; } } } return result; } };
#二级减枝
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> result; sort(nums.begin(), nums.end()); for (int k = 0; k < nums.size(); k++) { // 剪枝处理 if (nums[k] > target && nums[k] >= 0) { break; // 这里使用break，统一通过最后的return返回 } // 对nums[k]去重 if (k > 0 && nums[k] == nums[k - 1]) { continue; } for (int i = k + 1; i < nums.size(); i++) { // 2级剪枝处理 if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) { break; } // 对nums[i]去重 if (i > k + 1 && nums[i] == nums[i - 1]) { continue; } int left = i + 1; int right = nums.size() - 1; while (right > left) { // nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出 if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) { right--; // nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出 } else if ((long) nums[k] + nums[i] + nums[left] + nums[right] < target) { left++; } else { result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]}); // 对nums[left]和nums[right]去重 while (right > left && nums[right] == nums[right - 1]) right--; while (right > left && nums[left] == nums[left + 1]) left++; // 找到答案时，双指针同时收缩 right--; left++; } } } } return result; } };
二刷
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> result; sort(nums.begin(),nums.end()); int left,right; for(int i=0 ; i<nums.size() ;i++) { if(nums[i] > target && target >=0 ) break; if(i>0 && nums[i] == nums[i-1] ) continue; for(int j=i+1 ; j<nums.size() ;j++) { if(nums[i] + nums[j] > target && target > 0) break; if(j>i+1 && nums[j]==nums[j-1]) continue; left = j+1; right = nums.size()-1; while(left<right) { if((long)nums[i]+nums[j]+nums[left]+nums[right] > target ) right--; else if((long)nums[i]+nums[j]+nums[left]+nums[right] < target ) left++; else if((long)nums[i]+nums[j]+nums[left]+nums[right] == target ) { vector<int> tmp ={nums[i] ,nums[j] ,nums[left],nums[right]}; result.push_back(tmp); while(left<right && nums[right]==nums[right-1]) right--; while(left<right && nums[left]==nums[left+1]) left++; right--; left++; } } } } return result; } };
