1 问题
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
- 0 <= a, b, c, d < n
- a、b、c 和 d 互不相同
- nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
2 答案
自己写的，感觉没问题
class Solution:def fourSum(self, nums: List[int], target: int) -> List[List[int]]:n = len(nums)res = []nums.sort()for i in range(n):if i>0 and nums[i]==nums[i-1]:continuefor j in range(i+1, n):if j>1 and nums[j]==nums[j-1]:continueL = j+1R = n-1while L<R:if nums[i]+nums[j]+nums[L]+nums[R]==target:res.append([nums[i], nums[j], nums[L], nums[R]])if L<R and nums[L] == nums[L+1]:L+=1if L<R and nums[R] == nums[R-1]:R-=1if nums[i]+nums[j]+nums[L]+nums[R] > target:R-=1else:L+=1return res
总是写错一些地方，修改后可以运行
class Solution:def fourSum(self, nums: List[int], target: int) -> List[List[int]]:n = len(nums)res = []nums.sort()for i in range(n):if i>0 and nums[i]==nums[i-1]:continuefor j in range(i+1, n):if j-i>1 and nums[j]==nums[j-1]:continueL = j+1R = n-1while L<R:if nums[i]+nums[j]+nums[L]+nums[R]==target:res.append([nums[i], nums[j], nums[L], nums[R]])while L<R and nums[L] == nums[L+1]:L+=1while L<R and nums[R] == nums[R-1]:R-=1L+=1R-=1elif nums[i]+nums[j]+nums[L]+nums[R] > target: # 必须elifR-=1else:L+=1return res
官方解，加了许多优化和剪枝的方法
class Solution:def fourSum(self, nums: List[int], target: int) -> List[List[int]]:n=len(nums)if(not nums or n<4):return []nums.sort()res=[]for i in range(n-3):if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target): # 第一次遍历剪枝breakif(nums[i]+nums[-1]+nums[-2]+nums[-3]<target): # 第一次遍历剪枝，nums[-1]这里-1是指n-1continueif(i>0 and nums[i]==nums[i-1]):continuefor j in range(i+1,n-2):if(nums[i]+nums[j]+nums[j+1]+nums[j+2]>target): # 第二次遍历剪枝breakif(nums[i]+nums[j]+nums[-1]+nums[-2]<target): # 第二次遍历剪枝continueif(j-i>1 and nums[j]==nums[j-1]):continueL=j+1R=n-1while(L<R):if(nums[i]+nums[j]+nums[L]+nums[R]==target):res.append([nums[i],nums[j],nums[L],nums[R]])while(L<R and nums[L]==nums[L+1]):L=L+1while(L<R and nums[R]==nums[R-1]):R=R-1L=L+1R=R-1elif(nums[i]+nums[j]+nums[L]+nums[R]>target):R=R-1else:L=L+1return res
