0015-3sum.py

classSolution:
defThreeSum(self, integers):
"""
 :type integers: List[int]
 :rtype: List[List[int]]
 """
integers.sort()
result= []
forindexinrange(len(integers)):
ifintegers[index] >0:
break
ifindex>0andintegers[index] ==integers[index-1]:
continue
left, right=index+1, len(integers) -1
whileleft<right:
ifintegers[left] +integers[right] <0-integers[index]:
left+=1
elifintegers[left] +integers[right] >0-integers[index]:
right-=1
else:
result.append([integers[index], integers[left], integers[right]]) # After a triplet is appended, we try our best to incease the numeric value of its first element or that of its second.
left+=1# The other pairs and the one we were just looking at are either duplicates or smaller than the target.
right-=1# The other pairs are either duplicates or greater than the target.
# We must move on if there is less than or equal to one integer in between the two integers.
whileintegers[left] ==integers[left-1] andleft<right:
left+=1# The pairs are either duplicates or smaller than the target.
returnresult