(难度Medium) Problem 18: 4Sum

Problem 18: 4Sum

链接

https://leetcode.com/problems/4sum/submissions/

Medium

题干

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.

样例

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]
]

题解

vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> ret;
int n = nums.size();
// 特判
if (n < 4) return ret;
// 排序
sort(nums.begin(), nums.end());

for (int i = 0; i < n-3; i++) {
if (i > 0 && nums[i] == nums[i-1]) continue;
vector<int> tmp;
// 复制数组i后面的部分，也可以不复制通过下标控制
tmp.assign(nums.begin()+i+1, nums.end());

// 进行3Sum
vector<vector<int>> cur = threeSum(tmp, target-nums[i]);
if (!cur.empty()) {
for (vector<int> vt : cur) {
vt.push_back(nums[i]);
ret.push_back(vt);
}
}
}
return ret;
}


vector> threeSum(vector& nums, int target) {
vector> ret;
int n = nums.size();
vector vt;

    // 遍历第一个数i
for (int i = 0; i < n-2 ; i++) {
// 使用two pointers算法来缩放数组
int l = i+1;
int r = n-1;
// 如果元素重复则跳过
if (i > 0 && nums[i] == nums[i-1]) continue;
while (l < r) {`