# [leetcode题解]17.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]
]

[
[-1,  0, 0, 1],
[-2, -1, 1, 2],
[-2,  0, 0, 2]
]

```class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
int i = 0, j = 0;
int le = 0, ri = 0;
int tmp_target = 0;
int sum = 0;
vector<int> four_nums;

sort(nums.begin(), nums.end());
for (i = 0; i < nums.size(); i++) {
if (i > 0 && nums[i] == nums[i - 1])
continue;

for (j = i + 1; j < nums.size(); j++) {
if (j > i + 1 && nums[j] == nums[j - 1])
continue;

le = j + 1;
ri = nums.size() - 1;
tmp_target = target - nums[i] - nums[j];

while (le < ri) {
sum = nums[le] + nums[ri];
if (le > j + 1 && nums[le] == nums[le - 1]) {
le++;
continue;
}
if (sum < tmp_target) {
le++;
} else if (sum > tmp_target) {
ri--;
} else {
four_nums.clear();
four_nums.push_back(nums[i]);
four_nums.push_back(nums[j]);
four_nums.push_back(nums[le]);
four_nums.push_back(nums[ri]);
res.push_back(four_nums);
le++;
ri--;
}
}
}
}
return res;
}
private:

};```