# Two Sum II - Input Array Is Sorted

## # Solution

### # Two Pointers

This is the best and most straightforward solution.

Complexity:

• time:
• space:
def twoSum(self, nums: List[int], target: int) -> List[int]:
left, right = 0, len(nums)-1
while left<right:
sm = nums[left] + nums[right]
if sm<target:
left += 1
elif sm>target:
right -= 1
else:
return [left+1,right+1]
return []


### # Dictionary

Like one-pass HashMap in Two Sum, a dictionary is used to store mappings from val to idx.

Complexity:

• time:
• space:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dct = {}
for idx,val in enumerate(nums):
if target-val in dct:
return [dct[target-val]+1, idx+1]
dct[val] = idx
return [-1,-1]


For each nums[i], use binary search to find target-nums[i].

Complexity:

• time:
• space:
def twoSum(self, nums: List[int], target: int) -> List[int]:
n = len(nums)

for i in range(n):
left, right = i+1, n-1
complement = target-nums[i]
while left<=right:
mid = left + (right-left)//2
if nums[mid] < complement:
left = mid + 1
elif nums[mid] > complement:
right = mid - 1
else:
return [i+1, mid+1]
return [-1, -1]

Last Updated: 5/18/2020, 9:42:35 AM