暴力法
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
if len(nums) < 4:
return []
nums.sort()
N = len(nums)
res = []
for i in range(N-3):
for j in range(i+1, N-2):
for k in range(j+1, N-1):
for m in range(k+1, N):
tmp = [nums[i], nums[j], nums[k], nums[m]]
if sum(tmp) == target and tmp not in res:
res.append(tmp)
return res
双指针
class Solution:
def Nsum(self, nums: List[int], N, start, target):
"""
Params:
nums: 输入列表
n: 求几个数之和,n=2 两数之和, n=3三数之和
start: 从列表的第几个元素开始搜索
target: 之和要为多少
"""
nums.sort()
res = []
n = len(nums)
# 至少是 2Sum,且数组大小不应该小于 n
if n < 2 or n < N:
return res
# 2Sum 是 base case
if N == 2:
lo, hi = start, n - 1
while lo < hi:
left, right = nums[lo], nums[hi]
if left + right == target:
res.append([left, right])
# 左边相同的元素移动
while lo < hi and nums[lo] == left:
lo += 1
# 左边相同的元素移动
while lo < hi and nums[hi] == right:
hi -= 1
elif left + right > target:
while lo < hi and nums[hi] == right:
hi -= 1
elif left + right < target:
while lo < hi and nums[lo] == left:
lo += 1
# n > 2 时,递归计算 (n-1)Sum 的结果
else:
i = start
# 遍历整个列表
while i < n:
left = nums[i]
sub = self.Nsum(nums, N-1, i+1, target-nums[i])
for item in sub:
res.append([left] + item)
while i < n and nums[i] == left:
i += 1
return res
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
res = self.Nsum(nums, 4, 0, target)
return res