class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: nums.sort() res = [] mem = set() for i in range(len(nums)): if nums[i] > 0: break if i > 0 and nums[i-1] == nums[i]: continue left_ptr, right_ptr = i + 1, len(nums) - 1 while left_ptr < right_ptr: if nums[i] + nums[left_ptr] > 0: break tmp_res = nums[i] + nums[left_ptr] + nums[right_ptr] if tmp_res == 0 and (nums[i], nums[left_ptr], nums[right_ptr]) not in mem: res.append([nums[i], nums[left_ptr], nums[right_ptr]]) mem.add((nums[i], nums[left_ptr], nums[right_ptr])) while left_ptr < right_ptr and nums[left_ptr] == nums[left_ptr+1]: left_ptr += 1 while left_ptr < right_ptr and nums[right_ptr] == nums[right_ptr-1]: right_ptr -= 1 left_ptr += 1 right_ptr -= 1 elif tmp_res < 0: left_ptr += 1 else: right_ptr -= 1 return res
分析
典型的双指针问题。
如果用暴力搜索需要O(n**3)的时间开销。
如果采用排序+双指针,理论上排序后双指针暴力也是O(n**3),但排序后适当选择指针位置可以剪枝。
剪枝的逻辑有3个。
第一个,最外层nums[i]如果大于0,那么nums[left_ptr]和nums[right_ptr]必然大于0;
第二个,如果nums[i] == nums[i-1],那证明相同的组合已经被搜索过;
第三个,跟第二个类似,如果nums[left_ptr] == nums[left_ptr+1],或者nums[right_ptr] == nums[right_ptr-1],那么证明相同的组合已经被搜索过;
标签:right,15,nums,三数,leetcode,res,指针,ptr,left From: https://www.cnblogs.com/bjfu-vth/p/18056579