Reference: LeetCode
Difficulty: Easy

Problem

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

• You may assume that each input would have exactly one solution and you may not use the same element twice.

Example:

Analysis

Brute-Force

Time: $O(N^2)$
Space: $O(1)$

Hash Table

Two-Pass:

One-Pass:

Time: $O(N)$
Space: $O(N)$

Note: Since we can only use each element once, lo is initially set as i + 1.

Time: $O(\log{N!}) = O(N\log{N})$
Space: $O(1)$

Two Pointers

Time: $O(N)$
Space: $O(1)$

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.