提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

双指针日渐熟练ing

一、题目

四数之和

给你一个由 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
你可以按 任意顺序 返回答案 。

示例

示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示

1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

二、思路

根据之前写的三数之和，这次固定前两个数，后两个数用双指针，时间复杂度O（n^3）。问题是还是不会去重，导致AC得很丑。

去重的方法是：同一层循环中，如果上一个元素和下一个元素相等，则跳过下一个元素。
注意，对于i和j，每重循环的第一个元素的上一个元素不是本层元素，因此判断的时候要把它跳过去。
对于双指针元素，只需要关注成功的情况下如果去重，因为只有成功的部分出现重复数字才会对结果产生影响，不成功的部分反正下轮也会过去。匹配成功时，low和high同时前移＋后移，因为不会有移动一个且产生新结果的情况（4数之和确定三个，剩下的一个一定是确定的）。

三、代码

1.暴力去重（if not in）（python）

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        #固定前两个元素（遍历，然后使用双指针）
        nums.sort() #排序 
        n=len(nums) #长度
        re_list=[] #返回数组
        #遍历
        for i in range(n-3):
            for j in range(i+1,n-2):
                low=j+1
                high=n-1
                temp=nums[i]+nums[j]
                while(low<high):#双指针
                    if(temp+nums[low]+nums[high]<target):
                        low+=1
                    elif(temp+nums[low]+nums[high]>target):
                        high-=1
                    else:
                        x=[nums[i],nums[j],nums[low],nums[high]]
                        if(x not in re_list):#去重
                            re_list.append(x)
                        low+=1
        #返回
        return re_list

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

2.优雅去重（python）

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        #固定前两个元素（遍历，然后使用双指针） 
        nums.sort() #排序 
        n=len(nums) #长度
        re_list=[] #返回数组
        #遍历
        for i in range(n-3):
            if(i>0 and nums[i]==nums[i-1]):#去重,从本层第二个元素开始
                continue
            for j in range(i+1,n-2):
                if(j>i+1 and nums[j]==nums[j-1]):#去重
                    continue
                low=j+1
                high=n-1
                while(low<high):#双指针
                    temp=nums[i]+nums[j]+nums[low]+nums[high]
                    if(temp<target):
                        low+=1
                    elif(temp>target):
                        high-=1
                    else:#匹配成功时
                        x=[nums[i],nums[j],nums[low],nums[high]]
                        re_list.append(x)
                        low+=1 #移动左指针
                        while(low<high and nums[low]==nums[low-1]):
                            low+=1
                        high-=1#移动右指针
                        while(low<high and nums[high]==nums[high+1]):
                            high-=1                 
        #返回
        return re_list
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