18.四数之和

发表于： 分类于：
字数： 1244 阅读：≈ 3分钟

18.四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n a、b、c 和 d 互不相同 nums[a] + nums[b] + nums[c] + nums[d] == target 你可以按 任意顺序 返回答案 。

思路

基本思想

相比于 15题 ，本题就是多了一个数，并且数的和不再是0而是target，但是基本的思路还是一样的，只需要将三数之和进行简单的改造，如果题解看不懂，需要先看15题的题解

将问题分解，四数之和分成一个数与三个数的和，这样问题就变成了三数之和的问题

只是三数之和的目标不再是0，而是target-nums[i],这个nums[i]就是第四个数，这四个数相加刚好是target

为了实现一个数与三个数的和，首先需要从nums中取出一个数，然后从余下的元素中使用三数之和的方法找出符合条件的数组成四元组

从nums中取出元素的操作，需要注意去重，也就是说不能从相同的元素开始搜索

整道题的逻辑就是建立在 15题 的基础上，只是编写代码时需要注意细心

核心的地方有两点：

  1. 去重的时候有三个地方都需要去重

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

    //第一次去重
if(nums[i]>target&&nums[i]>0)
    break;
if(i>0&&nums[i]==nums[i-1])
    continue;

//第二次去重，仿照第一次去重的经验    
if(nums[j] + nums[i] > target && nums[j] + nums[i] >= 0)
    break;
//防止从重复的元素出发搜索剩下的元素
if(j>i+1&&nums[j]==nums[j-1])
    continue;

//第三次去重
while(left<right&&nums[right]==nums[right-1])
    right--;
while(left<right&&nums[left]==nums[left+1])
    left++;

  2. 四数之和可能超过int的范围，需要类型转换

    1

    long sum=(long)nums[i]+nums[j]+nums[left]+nums[right];

剩下的都仿照15题即可

执行流程

  1. 对元素进行排序
  2. 从第一个元素出发，搜索剩下的三个元素，出发时需要去重，第一次去重
  3. 从第二个元素出发，搜索剩下的两个元素，出发时需要去重，第二次去重
  4. 从余下的元素中搜索剩下的两个元素组成四元素，注意形成四元组之后，需要第三次去重
  5. 返回最终的结果

代码

根据以上分析，得出以下代码：

 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
50
51
52
53
54
55
56
57
58
59

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        //分解成一个数与三个数的和，尝试从三数之和中找出target-nums[i]的数出来
        //如何判断元素不能重复
        sort(nums.begin(),nums.end());
        vector<vector<int>> res;
        for(int i=0;i<nums.size();++i){
            //第一次去重
            if(nums[i]>target&&nums[i]>0)
                break;
            if(i>0&&nums[i]==nums[i-1])
                continue;
            //j从i+1出发，防止下标重复
            for(int j=i+1;j<nums.size();++j){
                //第二次去重
                //按照去重的逻辑,此时有两个元素
                //当两个元素相加大于target，并且两个元素相加都大于0了
                //说明后面的元素肯定都大于0
                if(nums[j] + nums[i] > target && nums[j] + nums[i] >= 0)
                    break;
                //防止从重复的元素出发搜索剩下的元素
                if(j>i+1&&nums[j]==nums[j-1])
                    continue;
                //从余下的元素中试图搜索出符合要求的元素
                int left=j+1;
                int right=nums.size()-1;
                while(left<right){
                    //对比三数之和与target-nums[i]的关系
                    long sum=(long)nums[j]+nums[left]+nums[right];
                    if(sum>target-nums[i])
                        right--;
                    else if(sum<target-nums[i])
                        left++;
                    else{
                        //第三次去重
                        //找到满足条件的元素，需要去重，防止出现重复的四元组
                        while(left<right&&nums[right]==nums[right-1])
                            right--;
                        while(left<right&&nums[left]==nums[left+1])
                            left++;
                        vector<int> temp;
                        temp.push_back(nums[i]);
                        temp.push_back(nums[j]);
                        temp.push_back(nums[left]);
                        temp.push_back(nums[right]);

                        res.push_back(temp);
                        //只要left<right，就一直尝试搜索合法的四元组
                        left++;
                        right--;
                    }
                }
            }
        }
        //返回最终的结果
        return res;
    }
};

总结

问题分割成一个数与另外三个数的和，三个数的和可以应用 15题 的解法，只是在15题的解法上需要再加一层for循环，所以最终需要两层for循环，并且两层for循环起始点不可以相同，防止出现相同的四元组