【leetcode系列】【py3】【中等】三数之和
题目:
题目链接: https://leetcode-cn.com/problems/3sum/
解题思路:
双指针
先对数组进行排序(快排),然后开始遍历
先固定最左边的一个数字,假设下标为index
对固定数字的右半部分,使用双指针遍历,开始时的left= index + 1, right= len(nums) - 1
当前的三数之和sum = nums[index] + nums[left] + nums[right],然后进行如下判断:
- 如果nums[index] > 0,则left和right如何移动,都无法使三数之和为0,直接退出所有循环
- 如果sum > 0 并且 nums[left] > 0,则表示当前固定的index,和剩余数字组合成的三数之和,都大于0,进行下一次循环,index = index + 1
- 如果left = right,进行下一次循环,index = index + 1
- 如果sum = 0,记录当前的三个数字,并进行下记操作
- 向右移动left,直到nums[left] != nums[left - 1]
- 向左移动right,直到nums[right] != nums[right + 1]
- 如果sum > 0,向左移动right
- 如果sum < 0,向右移动left
代码实现:
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums_len = len(nums)
if nums_len < 3:
return []
res = []
nums.sort()
if nums[0] > 0 or nums[-1] < 0:
return []
index = 0
for index in range(0, nums_len):
if nums[index] > 0:
break
elif index > 0 and nums[index] == nums[index - 1]:
continue
left, right = index + 1, nums_len - 1
while left < right:
curr_sum = nums[index] + nums[left] + nums[right]
if curr_sum == 0:
res.append([nums[index], 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 curr_sum > 0:
right -= 1
else:
left += 1
return res