3sumV2.py (1686B)
1 class Solution: 2 3 # IDEA: 4 5 # sort list 6 # a + b + c = 0 7 # a_index = 0 8 # for each a_index: 9 # b = val at next index 10 # c = len(nums) - 1 11 # for each b,c: 12 # check if prior b was same 13 # check if prior c was same 14 # if either were, test next selection of b,c 15 # next selection of b,c is where b_index += 1 or c_index -= 1 16 # depending on if the current guess is too high or low based on 17 # a + b + c 18 19 def threeSum(self, nums: List[int]) -> List[List[int]]: 20 21 nums.sort() 22 23 # a + b + c = 0 24 returnLs = [] 25 26 # -2 because b_index > a_index and c_index > b_index 27 for a_index in range(0, len(nums) - 2): 28 29 if a_index != 0 and nums[a_index] == nums[a_index - 1]: 30 continue 31 32 b_index = a_index + 1 33 c_index = len(nums) - 1 34 a = nums[a_index] 35 36 while c_index > b_index: 37 38 b = nums[b_index] 39 c = nums[c_index] 40 41 # b same as prior 42 if b_index - 1 != a_index and b == nums[b_index - 1]: 43 b_index += 1 44 continue 45 # c same as prior 46 if c_index != len(nums) - 1 and c == nums[c_index + 1]: 47 c_index -= 1 48 continue 49 50 sumbc = b + c 51 result = sumbc + a 52 53 if result == 0: 54 returnLs.append([a, b, c]) 55 c_index -= 1 56 b_index += 1 57 58 if result > 0: 59 c_index -= 1 60 61 if result < 0: 62 b_index += 1 63 64 return returnLs