87fdf5a82bb40ef0dc239815feac097f
(难度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.

题意

这道题叫做4sum,其实就是我们之前做的3sum的变形。给定一个数组array,和一个数target,要求所有的abcd四个数组合,使得a+b+c+d=target。注意,最后返回的答案当中需要保证没有重复的元素

样例

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

题解

盘点一下,到目前为止我们已经做过了2sum,3sum以及3sum的变种,其实这类题目都已经有规律了。

利用3sum的算法,很容易得到4sum的结果。也就是说我们枚举一个数a,然后从剩下的元素当中寻找3个数,使得这三个数的和相加等于target-a。而寻找这三个数的过程就是3Sum,之前没有做过3Sum问题的同学可以移步第15题:(难度Medium) Problem 15: 3Sum - 小专栏

利用3Sum,这道题非常简单:

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;
    }

代码当中的threeSum方法,就是我们之前15题当中的解法。主要思路是枚举一个元素,通过two pointers算法快速寻找另外两个。看不明白的同学可以移步之前的文章,完整的代码如下:

```
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) {
top Created with Sketch.