nathanwailes

LeetCode 15 - 3Sum - 2023.10.09 solution

Oct 8th, 2023
863
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.42 KB | None | 0 0
  1. class Solution:
  2.     def threeSum(self, nums: List[int]) -> List[List[int]]:
  3.         """ Thought process: this is like two-sum except the sum isn't zero.
  4.        
  5.        We don't care about the indices, just the actual values.
  6.  
  7.        To use the two-pointer-stepping-inwards method we need to sort the
  8.        input.
  9.  
  10.        We could just step through the list for the first number, then use
  11.        the two-pointer solution to find the other two numbers.
  12.        """
  13.         output = set()
  14.  
  15.         nums = sorted(nums)
  16.  
  17.         # [-1,0,1,2,-1,-4]
  18.         # [-4,-1,-1,0,1,2]
  19.         current_i = nums[0]
  20.         i = 0
  21.         while i < len(nums) - 2:
  22.             # use the two-pointer approach to find the other two numbers
  23.             j = i + 1
  24.             k = len(nums) - 1
  25.             while j < k:
  26.                 current_sum = nums[j] + nums[k] + nums[i]
  27.                 if current_sum == 0:
  28.                     output.add(tuple(sorted([nums[i], nums[j], nums[k]])))
  29.                     j += 1
  30.                     k -= 1
  31.                 elif current_sum < 0:
  32.                     j += 1
  33.                 elif current_sum > 0:
  34.                     k -= 1
  35.                
  36.             # increment the first number
  37.             while i < len(nums) and nums[i] == current_i:
  38.                 i += 1
  39.             if i >= len(nums):
  40.                 break
  41.             current_i = nums[i]
  42.         return list(output)
  43.  
Advertisement
Add Comment
Please, Sign In to add comment