# target: 0
# [-1, -1, 2, -1]
# -> [-1, -1, 2], [-1, 2, -1] choose one
# Approach
# For each number
# 1. target - nums[0]: 1
# 2. Find two number in the rest of array which sum to -1
# -> Become a smaller question. it is 2 sum
# Approach for twoSum:
# First sort the array.
# We can use binary search to find the solution.
# [-1, -1, 0, 1, 2] target = 0
# left: -1, right: 2 -> 1 and 1 > 0 the sum is too large
# left: -1, right: 1 -> 0 we found the target
class Solution:
def twoSum(self, nums: List[int], target) -> List[List[int]]:
left = 0
right = len(nums) - 1
res = []
while left < right:
leftNum = nums[left]
rightNum = nums[right]
total = leftNum + rightNum
if total == target:
res.append([leftNum, rightNum])
while left < right and leftNum == nums[left]:
left += 1
while left < right and rightNum == nums[right]:
right -= 1
elif total < target:
left += 1
elif total > target:
right -= 1
return res
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
if len(nums) <= 2:
return []
i = 0
while i < len(nums):
num = nums[i]
candidates = self.twoSum(nums[i+1:], 0 - num)
for candidate in candidates:
candidate.append(num)
res.append(candidate)
i += 1
while i < len(nums) and num == nums[i]:
i += 1
return res
