题目：三数之和（15） 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。 注意：答案中不可以包含重复的三元组。 思路： 1.先判断：数组是否为空，数组长度是否小于3 2.对数组进行排序 3.遍历数组，注意特殊情况： （1）如果nums[i]>0，则其后的数都大于0，其和不可能为0，直接返回结果 （2）对于重复元素，直接跳过，避免重复解 （3）对于指定的nums[i]，分三种情况讨论，即：nums[i]+nums[j]+nums[k]之和等于0，大于0，或小于0 （其中j=i+1，k=len(nums)-1)
解答：
class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: res=[] if not nums or len(nums)<3: return [] nums.sort() for i in range(len(nums)): if nums[i]>0: return res if i>0 and nums[i]==nums[i-1]: continue j=i+1 k=len(nums)-1 while j<k: if nums[i]+nums[j]+nums[k]==0: res.append([nums[i],nums[j],nums[k]]) while(j<k and nums[j]==nums[j+1]): j+=1 while(j<k and nums[k]==nums[k-1]): k-=1 j+=1 k-=1 elif nums[i]+nums[j]+nums[k]<0: j+=1 else: k-=1 return res题目：四数之和（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]]: res=[] n=len(nums) if not nums or n<4: return res nums.sort() for i in range(n-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[n-1]+nums[n-2]+nums[n-3]<target: while i<n-4 and nums[i]==nums[i+1]: i+=1 continue for j in range(i+1,n-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[n-1]+nums[n-2]<target: while j<n-3 and nums[j]==nums[j+1]: j+=1 continue s=j+1 t=n-1 new_target=target-nums[i]-nums[j] while s<t: if nums[s]+nums[t]==new_target: res.append([nums[i],nums[j],nums[s],nums[t]]) while s<t and nums[s]==nums[s+1]: s+=1 while s<t and nums[t]==nums[t-1]: t-=1 s+=1 t-=1 elif nums[s]+nums[t]<new_target: s+=1 else: t-=1 return res