求和系列题目
链接
https://leetcode-cn.com/problems/4sum/
题目
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
题目解析
这题和求 3 数之和的方法一样，只是多加一重循环。时间复杂度为 O(n^3)。
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
if len(nums) < 4:
return []
nums.sort()
res = set()
for i, iv in enumerate(nums[:-3]):
if i >= 1 and iv == nums[i - 1]:
continue
j = i + 1
while j < len(nums) - 2:
jv = nums[j]
if j > i + 1 and jv == nums[j - 1]:
j += 1
continue
start = j + 1
end = len(nums) - 1
while start < end:
if iv + jv + nums[start] + nums[end] == target:
res.add((iv, jv, nums[start], nums[end]))
start += 1
end -= 1
elif iv + jv + nums[start] + nums[end] > target:
end -= 1
else:
start += 1
j += 1
return list(map(list, res))
