LeetCode 18 4Sum

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

题意：

给出数组s和目标target，输出s中4个元素相加和为target的所有不同方案。

思路：

又是x sum问题，详见我的题解：http://blog.csdn.net/houserabbit/article/details/54707475

这题要注意的是去掉重复的方案，而且本题时间卡常数，代码要写的快一点。

代码：

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {sort(nums.begin(), nums.end());vector<vector<int>> ans;for(int i = 0; i < nums.size(); ++i){if(i != 0 && nums[i] == nums[i - 1]){continue;}for(int j = i + 1; j < nums.size(); ++j){if(j != i + 1 && nums[j] == nums[j - 1]){continue;}for(int l = j + 1, r = nums.size() - 1; l < r;){int sum = nums[i] + nums[j] + nums[l] + nums[r];if(sum == target){ans.push_back(vector<int>{nums[i], nums[j], nums[l], nums[r]});do{++l;}while(l < r && nums[l] == nums[l - 1]);do{--r;}while(l < r && nums[r] == nums[r + 1]);}else if(sum < target){do{++l;}while(l < r && nums[l] == nums[l - 1]);}else{do{--r;}while(l < r && nums[r] == nums[r + 1]);}}}}return ans;}
};

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

---