3sum.py (2075B)
1 class Solution: 2 # IDEA: 3 4 # O(n^2) time complexity 5 # pointer on left, pointer on right 6 # check if i in hashmap where i + left + right == 0 7 # if it is, add to output 8 # if it is not, continue on 9 # we do this for each selection of left and right indices 10 # we check O(n^2) possible combinations in constant time with 11 # the hashmap thus this is O(n^2) time complexity 12 13 # how to move the pointers? 14 # left pointer stays in place 15 # right pointer iterates 16 17 def threeSum(self, nums: List[int]) -> List[List[int]]: 18 19 nums.sort() 20 21 returnLs = [] 22 added = set() 23 24 for current_index in range(0, len(nums)): 25 current_value = nums[current_index] 26 left_ptr = current_index + 1 27 right_ptr = len(nums) - 1 28 29 while right_ptr > left_ptr: 30 31 if ( 32 right_ptr != len(nums) - 1 33 and nums[right_ptr] == nums[right_ptr + 1] 34 ): 35 right_ptr -= 1 36 continue 37 if ( 38 left_ptr != current_index + 1 39 and nums[left_ptr] == nums[left_ptr - 1] 40 ): 41 left_ptr += 1 42 continue 43 44 inverse = -(nums[right_ptr] + nums[left_ptr]) 45 if inverse == current_value: 46 cl = [nums[right_ptr], nums[left_ptr], current_value] 47 cl_string = str(cl) 48 if cl_string in added: 49 right_ptr -= 1 50 left_ptr += 1 51 continue 52 53 returnLs.append(cl) 54 added.add(cl_string) 55 if nums[right_ptr - 1] == nums[right_ptr]: 56 right_ptr -= 1 57 else: 58 left_ptr += 1 59 60 if current_value > inverse: 61 right_ptr -= 1 62 if current_value < inverse: 63 left_ptr += 1 64 65 return returnLs