Problem

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.

Notice that the solution set must not contain duplicate quadruplets.

Constraints:

0 <= nums.length <= 200-109 <= nums[i] <= 109-109 <= target <= 109

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/4sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Example1

Input: nums = [1,0,-1,0,-2,2], target = 0 Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example2

Input: nums = [], target = 0 Output: []

Solution

class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); vector<vector<int>> res; for (int i = 0; i < nums.size(); i ++ ) { if (i && 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 k = j + 1, u = nums.size() - 1; k < u; k ++ ) { if (k > j + 1 && nums[k] == nums[k - 1]) continue; while (u - 1 > k && nums[i] + nums[j] + nums[k] + nums[u - 1] >= target) u -- ; if (nums[i] + nums[j] + nums[k] + nums[u] == target) { res.push_back({nums[i], nums[j], nums[k], nums[u]}); } } } } return res; } };