leetcode with python:18. 4Sum

题目:

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.

给定一阵列和目标值(target)
回传阵列中所有取四数相加为target的可能,且不能包含重複的可能

又一题15.的类题
只要将其中一值固定,就相当于在找3sum
再将其中一值固定,就相当于在找2sum

class Solution:    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:        if len(nums)<4:            return []                ans=[]        nums=sorted(nums)                for i in range(len(nums)-3):            for j in range(i+1,len(nums)-2):                aim=target-nums[i]-nums[j]                l=j+1                r=len(nums)-1                while l<r:                    if nums[l]+nums[r]>aim:                        r=r-1                    elif nums[l]+nums[r]<aim:                        l=l+1                    else:                        if [nums[i],nums[j],nums[l],nums[r]] not in ans:                            ans.append([nums[i],nums[j],nums[l],nums[r]])                        l=l+1                        while l<r and nums[l-1]==nums[l]:                            l=l+1                    return ans

类似的操作就不再赘述,详细可看15.
让阵列的值轮流当固定值,对固定值右侧的元素做3sum操作
但多层的迴圈让加速程式的机制难以撰写
所以上述的版本我并未添加加速机制,因此效能也较低
最后执行时间983ms(faster than 62.98%)

讨论区有人使用递迴实作,不仅让程式看起来更有条理
也让加速机制的撰写更为方便
此解法不只能用在4sum,5sum,6sum都能用相同的函式解决

class Solution:    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:        nums.sort()        ans=[]        temp=[]                def ksum(target,start,k):            if len(nums) < k or k < 2 or target < nums[start]*k or target > nums[-1]*k:                return            if k!=2:                for i in range(start,len(nums)-k+1):                    if i>start and nums[i]==nums[i-1]:                        continue                    temp.append(nums[i])                    ksum(target-nums[i],i+1,k-1)                    temp.pop()                return                        l=start            r=len(nums)-1            while l<r:                if nums[l]+nums[r]<target:                    l=l+1                elif nums[l]+nums[r]>target:                    r=r-1                else:                    ans.append(temp+[nums[l],nums[r]])                    l=l+1                    while l<r and nums[l-1]==nums[l]:                        l=l+1                    ksum(target,0,4)        return ans

先将阵列排序方便操作
该递迴函式(ksum)有三个输入值,目标值(target),起始位置(start),要求几sum(k表ksum)
透过递迴程式的加速机制更好制定:
当发现target < nums[start] * k 或 target > nums[-1] * k
就直接return提早结束该次递迴

若k大于2,则将start以后的值轮流当固定值
将固定值放入temp供后续使用
接着执行ksum(target-固定值,固定值位置+1,k-1),进入下一阶段
执行完将temp内的值pop掉

若k等于2,则开始用两端指标求符合条件的组合(详见15.)
若有找到则在ans填入temp+[nums[l],nums[r]] (即其中一种4sum组合)

函式完全结束后回传ans
最后执行时间84ms(faster than 98.83%)

那我们下题见