四数之和

题目链接

注意：
答案中不可以包含重复的四元组
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

题目解析

对于python来说有个取巧的方法是利用itertools，先获得所有不重复组合，再判断每个组合是否等于target，这里不再赘述。本文介绍解这类问题的一般方法，指针法，可扩展至寻找两数之和、三数之和等等问题。

解题方法

借鉴双指针法，利用两个指针不断逼近，从而遍历所有可能组合。对于四数之和问题，我们仅需要添加两个辅助指针。因此，我们需要a,b,c,d四个指针，它们的关系为$a< b< c< d$。

如何使用双指针

我们需要先确定a和b的值，从而确定使用双指针法的边界。指针满足如下条件（size为列表长度）:

• a:[0,size-3]
• b:[a+1,size-2]
• c:[b+1] 双指针左边界
• d:[size-1] 双指针右边界

解决重复问题

考虑如下例子:[1, 0, -1, 0, -2, 0, 2]，target=0
使用上述指针遍历每组情况时，无法避免[1,0,-1,0]和[1,0,-1,0]这里两个0分别为index为3和5位置的0。
因此，我们需要先将列表排序，并且在移动指针时，判断当前值与上一个所指的值是否相同，进而去除相同值重复遍历的情况。

剪枝

本题的搜索空间极大，计算复杂度为$O(N^4)$，若不加剪枝，很容易造成超时。
剪枝条件也较为简单，在排序后，nums[a]< nums[b]< nums[c] < nums[d], 在给定a和b后，我们可以计算出当前a、b组合下的最小值和最大值。
对于给定a

• 最小值 $min=nums[a]+nums[a+1]+nums[a+2]+nums[a+3]$ if min > target : break ，最小值都大于target，不存在解
• 最大值 $max=nums[a]+nums[size-3]+nums[size-2]+nums[size-1]$ if max < target : continue，遍历下一个a，增大可能的最大值。

对于给定的a和b

• 最小值 $min=nums[a]+nums[b]+nums[b+1]+nums[b+2]$ if min > target : break
• 最大值 $max=nums[a]+nums[b]+nums[size-2]+nums[size-1]$ if max < target : continue

注意这里没有考虑重复值，是因为即使这样的绝对最小值都不满足情况，后续肯定不用继续遍历。

解题代码

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        #四个指针
        #先排序
        nums.sort()
        print(nums)
        size=len(nums)
        result=[]
        #指针a
        for a in range(0,size-3):
            #避免重复
            if a>0 and nums[a-1]==nums[a]:
                continue
            #剪枝
            if target < nums[a] + nums[a+1] + nums[a+2] + nums[a+3]:
                #当前最小值都大于target 那后面肯定也不用遍历了
                break
            if target > nums[a] + nums[size-3] + nums[size-2] + nums[size-1]:
                #当前最大值都小于target 那也不用遍历了
                continue
            for b in range(a+1,size-2):
                #避免重复
                if b>a+1 and nums[b-1]==nums[b]:
                    continue
                #剪枝
                if target < nums[a] + nums[b] + nums[b+1] + nums[b+2]:
                    #当前最小值都大于target 那后面肯定也不用遍历了
                    break
                if target > nums[a] + nums[b] + nums[size-2] + nums[size-1]:
                    #当前最大值都小于target 那也不用遍历了
                    continue
                #双指针
                #c=b+1 d=size-1 从两端包夹求解
                c = b+1
                d = size-1
                while c<d:
                    cur_sum=nums[a] + nums[b] + nums[c] + nums[d]
                    if cur_sum==target:
                        result.append([nums[a],nums[b],nums[c],nums[d]])
                        c += 1
                        d -= 1
                        while c < d and nums[c] == nums[c - 1]: c += 1 # 避免结果重复
                        while c < d and nums[d] == nums[d + 1]: d -= 1 
                    elif cur_sum < target:
                        c+=1
                    else:
                        d-=1
        return result

总结

指针法可以快速遍历数组的所有情况，因此对于求解列表上的所有解空间，可以考虑使用指针法，利用双指针来包夹求解。