three_sum.py

"""
https://en.wikipedia.org/wiki/3SUM
"""


defthree_sum(nums: list[int]) ->list[list[int]]:
"""
 Find all unique triplets in a sorted array of integers that sum up to zero.

 Args:
 nums: A sorted list of integers.

 Returns:
 A list of lists containing unique triplets that sum up to zero.

 >>> three_sum([-1, 0, 1, 2, -1, -4])
 [[-1, -1, 2], [-1, 0, 1]]
 >>> three_sum([1, 2, 3, 4])
 []
 """
nums.sort()
ans= []
foriinrange(len(nums) -2):
ifi==0or (nums[i] !=nums[i-1]):
low, high, c=i+1, len(nums) -1, 0-nums[i]
whilelow<high:
ifnums[low] +nums[high] ==c:
ans.append([nums[i], nums[low], nums[high]])

whilelow<highandnums[low] ==nums[low+1]:
low+=1
whilelow<highandnums[high] ==nums[high-1]:
high-=1

low+=1
high-=1
elifnums[low] +nums[high] <c:
low+=1
else:
high-=1
returnans


if__name__=="__main__":
importdoctest

doctest.testmod()