leetcode 3Sum python

时间:2023-03-08 15:24:00
leetcode 3Sum python
# sort the array
# loop from i = 0
# then left=i+1 right=len(nums)-1
# try nums[i] - ( nums[left]+nums[right]) = 0
# class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res=list()
nums.sort()
if len(nums) <= 2:
return res for index in range(len(nums)-2):
if index == 0 or nums[index] > nums[index-1]:
left=index+1
right=len(nums)-1
while left < right:
if nums[left] + nums[right] == -nums[index]:
res.append( [nums[index],nums[left],nums[right] ] )
left+=1
right-=1
              #ensure no repeat value
while left<right and nums[left] == nums[left-1]:
left+=1
while left < right and nums[right] == nums[right+1]:
right-=1
elif nums[left] + nums[right] < -nums[index]: while left < right:
left+=1
if nums[left] != nums[left-1]:
break
else:
while left < right:
right-=1
if nums[right] != nums[right+1]:
break
return res

@link http://www.cnblogs.com/zuoyuan/p/3699159.html