[LeetCode-Python版]相向双指针——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
你可以按 任意顺序 返回答案 。

示例 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
• $-10^9<=nums[i]<=10^9$
• $-10^9<=target<=10^9$

思路

思路和 15. 三数之和 一样，排序后，枚举 nums[a] 作为第一个数，枚举 nums[b] 作为第二个数，那么问题变成找到另外两个数，使得这四个数的和等于 target，这可以用双指针解决。

时空复杂度

时间复杂度：$O(n^3)$
空间复杂度：$O(1)$

参考代码

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        res = []

        for a in range(len(nums)-3):
            if a and nums[a]==nums[a-1]:
                continue

            if nums[a]+nums[a+1]+nums[a+2]+nums[a+3] >target:
                break
            if nums[a]+nums[-1]+nums[-2]+nums[-3] < target:
                continue
            for b in range(a+1,len(nums)-2):
                if b>a+1 and nums[b]==nums[b-1]:
                    continue
                c = b + 1
                d = len(nums)-1

                if nums[a]+nums[b]+nums[b+1]+nums[b+2] >target:
                    break
                if nums[a]+nums[-1]+nums[-2]+nums[b] < target:
                    continue

                while c<d:
                    s = nums[a]+nums[b]+nums[c]+nums[d]
                    if s>target:
                        d-=1
                    elif s<target:
                        c+=1
                    else:
                        res.append([nums[a],nums[b],nums[c],nums[d]])
                        c+=1
                        while c<d and nums[c]==nums[c-1]: 
                            c+=1
                        d-=1
                        while c<d and nums[d]==nums[d+1]:
                            d-=1
        return res