- 题目:给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。
- 类型:查找符合条件的三个数
- 思路:01-排序+for+双指针的结构;02-for和双指针都要去重;03-循环前和循环后都要剪枝。
- 经验:(1)单层for循环,break和return的作用一致;(2)当外层限制了left和right的关系,内层只更新left,一定要在内层的条件中加上left和right的关系,防止溢出。
def threeSum(self, nums: List[int]) -> List[List[int]]:
if not nums or len(nums)<3:return []
res=[]
nums=sorted(nums)
for i in range(len(nums)):
if i>0 and nums[i]==nums[i-1]:continue
if nums[i]+nums[i+1]+nums[i+2]>0:break
if nums[i]+nums[len(nums)-1]+nums[len(nums)-2]<0:continue
left=i+1
right=len(nums)-1
while left<right:
if (nums[i]+nums[left]+nums[right]==0):
res.append([nums[i],nums[left],nums[right]])
while left<right and nums[left]==nums[left+1]:left+=1
while left<right and nums[right]==nums[right-1]:right-=1
left+=1
right-=1
elif nums[i]+nums[left]+nums[right]<0:left+=1
else:right-=1
return res
明日计划: 11. 盛最多水的容器:双指针 633. 平方数之和
|