18. 4 Sum

本文主要是介绍18. 4 Sum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

解答：

与之前的三数之和的解法类似，也是先排序，然后不断剔除不可能的条件，最后两个参数，通过两头求和计算得出。

代码：

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> result;int len = nums.size();if(len < 4) return result;sort(nums.begin(), nums.end());for(int i = 0;i < len - 3;){if(nums[i] * 4 > target)    break;for(int j = i + 1;j < len - 2;){if((nums[i] + nums[j]) * 2 > target)  break;int remain = target - nums[i] - nums[j];int begin = j + 1, end = len - 1;while(begin < end){int tmp = nums[begin] + nums[end];if(tmp > remain){while(begin < end && nums[end-1] == nums[end])--end;--end;}else if(tmp < remain){while(begin < end && nums[begin+1] == nums[begin])++begin;++begin;}else{vector<int> vec({nums[i], nums[j], nums[begin], nums[end]});result.push_back(vec);while(begin < end && nums[end-1] == nums[end])--end;while(begin < end && nums[begin+1] == nums[begin])++begin;--end, ++begin;}}while(j < len - 2 && nums[j+1] == nums[j])    ++j;++j;}while(i < len - 3 && nums[i+1] == nums[i])  ++i;++i;}return result;}
};

更新会同步在我的网站更新(https://zergzerg.cn/notes/webnotes/leetcode/index.html)

这篇关于18. 4 Sum的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---