四数之和

题目链接

题目原文 给定一个包含 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]
]

题目解析

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

解题方法

借鉴双指针法,利用两个指针不断逼近,从而遍历所有可能组合。对于四数之和问题,我们仅需要添加两个辅助指针。因此,我们需要a,b,c,d四个指针,它们的关系为a<b<c<da< 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(N4)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]min=nums[a]+nums[a+1]+nums[a+2]+nums[a+3] if min > target : break ,最小值都大于target,不存在解
  • 最大值 max=nums[a]+nums[size3]+nums[size2]+nums[size1]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]min=nums[a]+nums[b]+nums[b+1]+nums[b+2] if min > target : break
  • 最大值 max=nums[a]+nums[b]+nums[size2]+nums[size1]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

总结

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