題目鏈接：國際版命浴，國內(nèi)版
公司：Meta
解法：雙指針问窃、遞歸
題目描述
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 < na, b, c, and d are distinct.nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Example 2:
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]
思路
如果你已經(jīng)做過 2sum 和 3sum 了工禾，那么這道題的題目描述你應(yīng)該已經(jīng)很熟悉了炼蛤，即：在一個無序且有重復(fù)的數(shù)組中找到四個元素莫换，使它們的和為 0伊佃，返回所有可能的結(jié)果』篮粒看到這里蹲坷，我們首先先來回憶一下 3sum 的解法驶乾，即：將數(shù)組排好序，每次固定一個元素 nums[i]冠句，再在剩余的子數(shù)組 nums[i+1:] 中找 2sum 結(jié)果為 target - nums[i] 的兩個元素即可轻掩。那么以此類推，對于這道 4sum懦底，我們也可以將數(shù)組排好序之后固定一個元素唇牧，在剩下的數(shù)組元素中找 3sum。這種思路的參考代碼如下：
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
""" 固定住第一個元素聚唐，對后續(xù)元素進行threeSum丐重，注意去重 """
def three_sum(nums, start, target):
def two_sum(numbers, start_idx, target):
res = []
i, j = start_idx, len(numbers) - 1
while i < j:
tmp = numbers[i] + numbers[j]
left, right = numbers[i], numbers[j]
if tmp < target:
while i < j and numbers[i] == left: i += 1
elif tmp > target:
while i < j and numbers[j] == right: j -= 1
else:
res.append([i, j])
while i < j and numbers[i] == left: i += 1
while i < j and numbers[j] == right: j -= 1
return res
res = []
i = start
while i < len(nums):
tuples = two_sum(nums, i + 1, target - nums[i])
for j, k in tuples:
res.append([i, j, k])
while i < len(nums) - 1 and nums[i + 1] == nums[i]:
i += 1
i += 1
return res
nums.sort()
res = []
a = 0
while a < len(nums):
tuples = three_sum(nums, a + 1, target - nums[a])
for b, c, d in tuples:
res.append([nums[a], nums[b], nums[c], nums[d]])
while a < len(nums) - 1 and nums[a + 1] == nums[a]:
a += 1
a += 1
return res
這種解法可以解題，但存在一個問題杆查，即：如果面試的時候面試官問你 5sum扮惦、6sum 怎么寫，難道我們還能從 2sum 開始一層一層地寫下去么亲桦？為此我們再次觀察一下思路：求 4sum 我們需要知道 3sum崖蜜，求解 3sum 我們需要知道 2sum，求解 2sum 就可以直接在 O(N) 的時間內(nèi)算出來了客峭。因此豫领，求解 nSum 問題，我們需要知道 (n-1)Sum 的解舔琅，這就變成了一個遞歸的解法等恐。同時，遞歸的終止條件是 2sum备蚓。參考代碼如下：
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
"""通用解法"""
def nSum(nums, n, start, target):
res = []
if n < 2:
return res
if n == 2:
i, j = start, len(nums) - 1
while i < j:
curr = nums[i] + nums[j]
left, right = nums[i], nums[j]
if curr < target:
# 去重
while i < j and nums[i] == left:
i += 1
elif curr > target:
# 去重
while i < j and nums[j] == right:
j -= 1
else:
res.append([left, right])
# 去重
while i < j and nums[i] == left:
i += 1
while i < j and nums[j] == right:
j -= 1
return res
else:
i = start
while i < len(nums):
tmp = nSum(nums, n - 1, i + 1, target - nums[i])
for tmp_res in tmp:
tmp_res.append(nums[i])
res.append(tmp_res)
# 去重
while i < len(nums) - 1 and nums[i + 1] == nums[i]:
i += 1
i += 1
return res
nums.sort()
return nSum(nums, 4, 0, target)
我們這里定義了一個名為 nSum 的 helper function课蔬，它的作用就是對于給定的數(shù)組，從中找出 n 個數(shù)郊尝，使其和為 target二跋。退出條件如之前所述，是 n == 2 的時候流昏，就演變?yōu)榱?2sum扎即。當 n > 2 的時候，我們每次需要固定一個元素横缔，再在剩下的元素中尋找 (n-1)sum铺遂。對于返回的每一個可能的組合衫哥，我們將其拼裝成最后的結(jié)果茎刚，即在列表中加上所固定的那個元素即可。
對于時間復(fù)雜度分析撤逢，我們需要看遞歸樹的深度膛锭。假設(shè)數(shù)組長度為 N粮坞，我們要求 k sum，由于遞歸退出的條件是 k = 2初狰，因此總的遞歸樹深度應(yīng)該為 k - 1莫杈，時間復(fù)雜度應(yīng)該為 O(N^(k-1))。對于空間復(fù)雜度分析奢入，我們主要考慮遞歸需要的棧的空間筝闹。由于遞歸樹深度為 k -1，因此棧的空間復(fù)雜度應(yīng)該為 O(k-1)腥光，在最壞情況下 k 應(yīng)該等于 n关顷，則空間復(fù)雜度為 O(N)
