【三数之和】python,排序+双指针

暴力搜索3次方的时间复杂度，大抵超时

遇到不会先排序

排序+双指针

上题解

照做

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:res=[]n=len(nums)#排序降低复杂度nums.sort()k=0#留两个位置给双指针i,jfor k in range(n-2):if nums[k]>0:break#比较其和前一个元素是否相等，相等则跳过（防止重复）if k>0 and nums[k]==nums[k-1]:continuei=k+1j=n-1while i<j:sum=nums[k]+nums[i]+nums[j]if sum<0:i+=1#同样的结果了while i<j and nums[i]==nums[i-1]:i+=1elif sum>0:j-=1#一样while i<j and nums[j]==nums[j+1]:j-=1else:res.append([nums[k],nums[i],nums[j]])i+=1j-=1#samewhile i<j and nums[i]==nums[i-1]:i+=1while i<j and nums[j]==nums[j+1]:j-=1return res

过 

 

总结：

1. 数组排序
2. 固定一个数，开始双指针，第一个指针紧随其后，第二个指针逆序
3. 剪枝包括与前面的元素相比有没有相同，相同则跳过
4. 每次移动i/j都可以考虑刚刚那步的剪枝