18. 四数之和 - 力扣（LeetCode）

发表于 更新于 分类于 阅读次数： Disqus：

题目描述

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。 注意： 答案中不可以包含重复的四元组。 示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

题解

最直接的想法当然是四重循环，暴力求解，复杂度为[latex] O(n^4) [/latex]，直接拉进小黑屋。 因为做过二数之和，三数之和等题，想着能否题目转成已知的问题。因此下面的一个想法就诞生了，固定一个数a，然后问题转成求b + c + d = target - a三数之和的解，使用的方法是排序 + 双指针。然后再改变a找到所有解。

代码

时间复杂度为$o(n^3)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        //先排序
        sort(nums.begin(), nums.end());
        int len = nums.size(),beg, end, sum;
        vector<vector<int>>res;
        for(int i = 0; i < len - 3; ++i){
            if(i > 0 && nums[i] == nums[i - 1]){//去重
                continue;
            }
            for(int j = i + 1; j < len - 2; ++j){
                if(j > i + 1 && nums[j] == nums[j - 1]){//去重
                    continue;
                }
                beg = j + 1, end = len - 1;
                while(beg < end){
                    sum = nums[i] + nums[j] + nums[beg] + nums[end];
                    if(sum > target){
                        --end;
                        while(beg < end && nums[end] == nums[end + 1]){
                            --end;
                        }
                    }
                    else if(sum < target){
                        ++beg;
                        while(beg < end && nums[beg] == nums[beg - 1]){
                            ++beg;
                        }
                    }
                    else{
                        res.push_back({nums[i], nums[j], nums[beg], nums[end]});
                        ++beg;
                        while(beg < end && nums[beg] == nums[beg - 1]){
                            ++beg;
                        }
                    }
                }
            }
        }
        return res;
    }
};

执行结果

优化

借助大佬的思路，加入两个if判断，用时瞬间超过90%！ 1. 如果tmp = a + min{b + c + d}仍然大于target，则整个循环没有继续下去的必要了，后面的四数之和不小于tmp，即大于target。 2. 如果tmp = a + max{b + c + d}仍然小于target，则此趟循环可以continue。 具体见代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        //先排序
        sort(nums.begin(), nums.end());
        int len = nums.size(),beg, end, sum;
        vector<vector<int>>res;
        for(int i = 0; i < len - 3; ++i){
            if(i > 0 && nums[i] == nums[i - 1]){//去重
                continue;
            }
            //当数组最小值和都大于target 跳出
            if(nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target)
                break;
            //当数组最大值和都小于target,说明i这个数还是太小,遍历下一个
            if(nums[i] + nums[len-1] + nums[len-2] + nums[len-3] < target)
                continue;
            for(int j = i + 1; j < len - 2; ++j){
                if(j > i + 1 && nums[j] == nums[j - 1]){//去重
                    continue;
                }
                beg = j + 1, end = len - 1;
                while(beg < end){
                    sum = nums[i] + nums[j] + nums[beg] + nums[end];
                    if(sum > target){
                        --end;
                        while(beg < end && nums[end] == nums[end + 1]){
                            --end;
                        }
                    }
                    else if(sum < target){
                        ++beg;
                        while(beg < end && nums[beg] == nums[beg - 1]){
                            ++beg;
                        }
                    }
                    else{
                        res.push_back({nums[i], nums[j], nums[beg], nums[end]});
                        ++beg;
                        while(beg < end && nums[beg] == nums[beg - 1]){
                            ++beg;
                        }
                    }
                }
            }
        }
        return res;
    }
};

执行结果