本文主要是介绍LeetCode·18. 4Sum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:The solution set must not contain duplicate quadruplets.Example:Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.A solution set is:
[[-1, 0, 0, 1],[-2, -1, 1, 2],[-2, 0, 0, 2]
]思路：
3-sum基础上外加一层循环
代码：
class Solution {
public:vector<vector<int> > fourSum(vector<int>& nums, int target) {vector<vector<int> > vec;int Len = nums.size();if(Len == 0)return vec;sort(nums.begin(), nums.end());vector<int> v(4);for(int i = 0; i < Len-3; ++i){if(i > 0 && nums[i-1] == nums[i])continue;if(nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target)return vec;else if(nums[i] + nums[Len-3] + nums[Len-2] + nums[Len-1] < target)continue;v[0] = nums[i];for(int j = i+1; j < Len-2; ++j){if(j > i+1 && nums[j-1] == nums[j])continue;if(nums[i] + nums[j] + nums[j+1] + nums[j+2] > target)break;else if(nums[i] + nums[j] + nums[Len-2] + nums[Len-1] < target)continue;v[1] = nums[j];for(int L = j+1, R=Len-1; L < R;){if(L > j+1 && nums[L-1] == nums[L]){++L;continue;}if(nums[i] + nums[j] + nums[L]+nums[R] == target){v[2] = nums[L];v[3] = nums[R];vec.push_back(v);if(nums[L] != nums[R]){while(L < R && nums[++L] == nums[L-1]){};while(L < R && nums[--R] == nums[R+1]){};}else{break;}}else if(nums[i] + nums[j] + nums[L]+nums[R] > target){--R;}else{++L;}}}}return vec;
}
};结果：
这篇关于LeetCode·18. 4Sum的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
