三,四数之和（双指针）

作者

15. 三数之和

  1. class Solution:
  2.     def threeSum(self, nums: List[int]) -> List[List[int]]:
  3.         res=[]
  4.         nums=sorted(nums)
  5.         for i in range(len(nums)):
  6.             if i>0 and nums[i]==nums[i-1]:
  7.                 continue
  8.             if nums[i]>0:
  9.                 break
  10.             l=i+1
  11.             r=len(nums)-1
  12.             while r>l:
  13.                 total=nums[i]+nums[l]+nums[r]
  14.                 if total>0:
  15.                     r-=1
  16.                 elif total<0:
  17.                     l+=1
  18.                 else:
  19.                     res.append([nums[i],nums[l],nums[r]])
  20.                     while r>l and nums[l]==nums[l+1]:
  21.                         l+=1
  22.                     while r>l and nums[r]==nums[r-1]:
  23.                         r-=1
  24.                     l+=1
  25.                     r-=1
  26.         return res
  27. 排序数组：首先对数组进行排序，以便使用双指针方法。
  28. 遍历数组：使用一个循环遍历数组，每次选择一个元素作为三元组的第一个元素。
  29. 跳过重复元素：如果当前元素与前一个元素相同，则跳过，以避免重复的三元组。
  30. 初始化双指针：左指针 l 初始化为 i + 1，右指针 r 初始化为数组末尾。
  31. 双指针查找：使用双指针查找满足条件的三元组。
    • 如果三数之和小于 0，移动左指针以增加总和。
    • 如果三数之和大于 0，移动右指针以减少总和。
    • 如果找到一个三元组，添加到结果列表中，并跳过重复的元素。
  32. 返回结果：返回所有满足条件的三元组。

注意排序，注意跳过重复元素（在3.5部分都有体现），当nums[i]>0时直接结束

18. 四数之和

  1. class Solution:
  2.     def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
  3.         nums.sort()
  4.         res=[]
  5.         for i in range(len(nums)):
  6.             if nums[i]*4>target:
  7.                 break
  8.             if i>0 and nums[i]==nums[i-1]:
  9.                 continue
  10.             for l in range(i+1,len(nums)):
  11.                 if l>i+1 and nums[l]==nums[l-1]:
  12.                     continue
  13.                 if nums[i]+nums[l]*3>target:
  14.                     break
  15.                 left=l+1
  16.                 right=len(nums)-1
  17.                 while left<right:
  18.                     total=nums[i]+nums[l]+nums[left]+nums[right]
  19.                     if total>target:
  20.                         right-=1
  21.                     elif total<target:
  22.                         left+=1
  23.                     else :
  24.                         res.append([nums[i],nums[left],nums[right],nums[l]])
  25.                         while left<right and nums[left]==nums[left+1]:
  26.                             left+=1
  27.                         while left<right and nums[right]==nums[right-1]:
  28.                             right-=1
  29.                         left+=1
  30.                         right-=1
  31.         return res
  33.        表扬下自己，四行代码（6,7,13,14）让运行时间几乎减半，应该是进一步剪枝了

发表评论