Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution:
- def threeSum(self, nums: List[int]) -> List[List[int]]:
- """ Thought process: this is like two-sum except the sum isn't zero.
- We don't care about the indices, just the actual values.
- To use the two-pointer-stepping-inwards method we need to sort the
- input.
- We could just step through the list for the first number, then use
- the two-pointer solution to find the other two numbers.
- """
- output = set()
- nums = sorted(nums)
- # [-1,0,1,2,-1,-4]
- # [-4,-1,-1,0,1,2]
- current_i = nums[0]
- i = 0
- while i < len(nums) - 2:
- # use the two-pointer approach to find the other two numbers
- j = i + 1
- k = len(nums) - 1
- while j < k:
- current_sum = nums[j] + nums[k] + nums[i]
- if current_sum == 0:
- output.add(tuple(sorted([nums[i], nums[j], nums[k]])))
- j += 1
- k -= 1
- elif current_sum < 0:
- j += 1
- elif current_sum > 0:
- k -= 1
- # increment the first number
- while i < len(nums) and nums[i] == current_i:
- i += 1
- if i >= len(nums):
- break
- current_i = nums[i]
- return list(output)
Advertisement
Add Comment
Please, Sign In to add comment