167. Two Sum II - Input Array Is Sorted: Two Pointers & Hash Map
The two pointers solution works well with O(1) extra space:
1class Solution:
2 def twoSum(self, numbers: List[int], target: int) -> List[int]:
3 l, r = 0, len(numbers) - 1
4
5 while numbers[l] + numbers[r] != target:
6 if numbers[l] + numbers[r] < target:
7 l += 1
8 continue
9 elif numbers[l] + numbers[r] > target:
10 r -= 1
11 continue
12
13 return [l + 1, r + 1]
Two pointer problems are always that easy to implement.
I also had some fun with hash map, everybody likes hash map.
1class Solution:
2 def twoSum(self, numbers: List[int], target: int) -> List[int]:
3 # just for fun, does not meet O(1) extra space
4
5 d = {} # reverse idx lookup
6 for i, number in enumerate(numbers):
7 if d.get(target - number, -1) != -1:
8 return [d[target - number] + 1, i + 1]
9 else:
10 d[number] = i
11
12 return [-1, -1]
#Neetcode150 #Two-Pointers #Hashing #Python