给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
需要去重，剪枝能够进一步缩短时间。
from typing import * class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: res = [] nums.sort() for a in range(len(nums) - 3): if a > 0 and nums[a] == nums[a - 1]: continue for b in range(a + 1, len(nums) - 2): if b > a + 1 and nums[b] == nums[b - 1]: continue c, d = b + 1, len(nums) - 1 # 这里相当于是进行了部分剪枝 if nums[a] + nums[b] + nums[c] + nums[c - 1] > target: break if nums[a] + nums[b] + nums[d - 1] + nums[d] < target: continue while c < d: tem_sum = nums[a] + nums[b] + nums[c] + nums[d] if tem_sum == target: res.append([nums[a], nums[b], nums[c], nums[d]]) c += 1 d -= 1 while c < d and nums[c] == nums[c - 1]: c += 1 while c < d and nums[d] == nums[d + 1]: d -= 1 elif tem_sum > target: d -= 1 while c < d and nums[d] == nums[d + 1]: d -= 1 else: c += 1 while c < d and nums[c] == nums[c - 1]: c += 1 return res
