題目:

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%)

那我們下題見