18. 四数之和

难度中等572

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，**b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：

1
2
3
4
5
6
7
8
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

通过次数109,251

提交次数284,303

双指针法;主要要注意的是几个边界以及怎么去重的方法;

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
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        //双指针法;
        //比O(n^4)的暴力减少了一些重复的内容;
        //算法是:固定a,b=a+1,然后c,d双指针遍历;然后b++……;然后b结束外层循环a++;

        
        sort(nums.begin(),nums.end());
        vector<vector<int>>result;
        int size=nums.size();
        if(size<4)return result;
        int a,b,c,d;
        for(int a=0;a<=size-4;++a){
            if(a>0&&nums[a]==nums[a-1])continue;
            for(int b=a+1;b<=size-3;++b){
                if(b>a+1&&nums[b]==nums[b-1])continue;
                c=b+1;
                d=size-1;

                while(c<d){
                    if(nums[a]+nums[b]+nums[c]+nums[d]<target){
                        c++;
                    }else if(nums[a]+nums[b]+nums[c]+nums[d]>target){
                        d--;
                    }else{
                        result.push_back({nums[a],nums[b],nums[c],nums[d]});
                        while(c<d&&nums[c]==nums[c+1]){
                            c++;
                        }
                        while(c<d&&nums[d]==nums[d-1]){
                            d--;
                        }
                        c++;
                        d--;


                    }
                }

            }
        }
        return result;
        


    }
};