LeetCode 15: 3Sum题解(python)
程序员文章站
2022-06-05 20:13:52
Leetcode 42: Trapping Rain Water分类:Two pointers难度:M描述:给了一个数组,问数组中存不存在a, b, c三个元素,使a + b + c = 0。把这些数组都找出来。Given array nums = [-1, 0, 1, 2, -1, -4],A solution set is:[ [-1, 0, 1], [-1, -1, 2]]链接: 3Sum.思路:本题使用双指针法,遍历数组,然后每次遍历中使用前后指针搜索是否存在满足条件...
Leetcode 42: Trapping Rain Water
分类:Two pointers
难度:M
描述:给了一个数组,问数组中存不存在a, b, c三个元素,使a + b + c = 0
。把这些数组都找出来。
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
链接: 3Sum.
思路:
本题使用双指针法,遍历数组,然后每次遍历中使用前后指针搜索是否存在满足条件的a, b, c
。这个题有两个点需要注意:
1)排序。一定要先排序
2)重复元素处理。如果遇到重复的元素怎么办?在左右指针判断完记录后,可以略过重复项。
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if not nums or len(nums) < 3: 判断边界条件
return []
nums = sorted(nums)
res = []
i = 0
while i < len(nums): 此处用while循环是为了便于略过重复项。
left = i + 1
right = len(nums) - 1
summ = -nums[i]
while left < right:
if nums[left] + nums[right] == summ:
temp = [nums[i], nums[left], nums[right]] 记录
res.append(temp)
left += 1
right -= 1
while left < right and nums[left] == nums[left-1]:
left += 1
while left < right and nums[right] == nums[right+1]:
right -= 1 两处while循环用于略过左右指针的重复项。
elif nums[left] + nums[right] < summ:
left += 1
else:
right -= 1
while i < len(nums) - 1 and nums[i] == nums[i+1]: 略过重复项。
i += 1
i += 1 不可忽略i的自增
return res
个人总结:
1)本题有许多类似题型,如:16,18,259,611.
2)本题比较麻烦的地方在于重复项的处理。
2)双指针的题,大多数是两重循环(for + while)。除此之外,注意是否需要先排序。
本文地址:https://blog.csdn.net/Bourns_A/article/details/107358375