【leetcode07】15. 三数之和

作者
  1. class Solution:
  2.     def threeSum(self, nums: List[int]) -> List[List[int]]:
  3.         le=len(nums)
  4.         nums.sort()
  5.         b=[]
  6.         for i in range(0,le-2):
  7.             if  i>0 and nums[i] == nums[i - 1]:
  8.                 continue
  9.             l=i+1
  10.             r=le-1
  11.             while l<r:
  12.                 if -nums[l]==nums[r]+nums[i]:
  13.                     b.append([nums[l],nums[r],nums[i]])
  14.                     while l<r and nums[l]==nums[l+1] :
  15.                         l+=1
  16.                     while l<r and nums[r]==nums[r-1] :
  17.                         r-=1
  18.                     r-=1
  19.                     l+=1
  20.                 elif nums[l]+nums[r]+nums[i]>0:
  21.                     r-=1
  22.                 else:
  23.                     l+=1
  25.         return b
防止重复：
  • if i > 0 and nums[i] == nums[i - 1]:
  •                 continue
  • 跳过重复元素
  • l=i
  • 目的使三数有序，防止重复
  • result.append([nums[i], nums[left], nums[right]])
    # 跳过重复的 left
    while left < right and nums[left] == nums[left + 1]:
    left += 1
    # 跳过重复的 right
    while left < right and nums[right] == nums[right - 1]:
    right -= 1

#继续下一个
left += 1
right -= 1

防止溢出：

  •  while l<r and nums[l]==nums[l+1] :√
  •  while nums[l]==nums[l+1] and l<r:×
  • 用例：[0,0,0]

发表评论