题干
给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]
分析
这个题目思路还是比较简单的,暴力肯定是要pass,肯定超时,所以需要就是尽力的优化时间复杂度。所有元素肯定都要用到,O(n)应该就是时间复杂度的极限了。如何一遍遍历,找出所有的结果?先给元素排个序就OK了。
代码
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res =[]
i = 0
for i in range(len(nums)):
if i == 0 or nums[i]>nums[i-1]:
l = i+1
r = len(nums)-1
while l < r:
s = nums[i] + nums[l] +nums[r]
if s ==0:
res.append([nums[i],nums[l],nums[r]])
l +=1
r -=1
while l < r and nums[l] == nums[l-1]:
l += 1
while r > l and nums[r] == nums[r+1]:
r -= 1
elif s>0:
r -=1
else :
l +=1
return res
欢迎大家关注我的公众号
半亩房顶
网友评论