# 167. Two Sum II - Input array is sorted

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:

• Your returned answers (both index1 and index2) are not zero-based.
• 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
a software engineering cat
Newest Comments
loading...
Info
Article :
50
Total Count :
82.4k
UV :
PV :
Last Push :