18. 四数之和 给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
排序+双指针
class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: quadruplets = list() if not nums or len(nums) < 4: return quadruplets nums.sort() length = len(nums) for i in range(length - 3): if i > 0 and nums[i] == nums[i - 1]: continue if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target: break if nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target: continue for j in range(i + 1, length - 2): if j > i + 1 and nums[j] == nums[j - 1]: continue if nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target: break if nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target: continue left, right = j + 1, length - 1 while left < right: total = nums[i] + nums[j] + nums[left] + nums[right] if total == target: quadruplets.append([nums[i], nums[j], nums[left], nums[right]]) while left < right and nums[left] == nums[left + 1]: left += 1 left += 1 while left < right and nums[right] == nums[right - 1]: right -= 1 right -= 1 elif total < target: left += 1 else: right -= 1 return quadruplets