Two Pointer: threeSum python
Thu Sep 22 2022 01:29:14 GMT+0000 (UTC)
Saved by
@bryantirawan
#python
#neetcode
#twosum
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
result = []
nums.sort()
for i, a in enumerate(nums):
if i > 0 and a == nums[i - 1]: #this is so you don't reuse same value twice to avoid duplicates at end
continue
#next part is basically two sum
l, r = i + 1, len(nums) - 1
while l < r:
threeSum = a + nums[l] + nums[r]
if threeSum > 0:
r -= 1
elif threeSum < 0:
l += 1
else:
result.append([a, nums[l], nums[r]])
#only need to shift left pointer as right pointer will be moved by code above
l += 1
while nums[l] == nums[l - 1] and l < r:
l += 1
return result
#two sum solutions below for reference
def twoSum(numbers, target):
left = 0
right = len(numbers) - 1
compare = 0
for i in range(0, len(numbers)):
compare = numbers[left] + numbers[right]
if compare > target:
right -= 1
elif compare < target:
left += 1
elif compare == target:
return [left + 1, right + 1]
def twoSum(self, nums: List[int], target: int) -> List[int]:
num_dictionary = {}
for i in range(0, len(nums)):
number = nums[i]
if target - number not in num_dictionary:
#number will be key and index (i) will be value
#adding number to dictionary AFTER checking 1st value
#if [2, 1, 3] and target = 4, 4 -2 = 2 and 2 will be present in dictionary but we cannot use 2 + 2
num_dictionary[number] = i
elif target - number in num_dictionary:
return [i, num_dictionary[target - number]]
content_copyCOPY
Basically one 3 pointer and 2sum
https://leetcode.com/problems/3sum/submissions/
Comments