By Long Luo

This article is the solution 4 Approaches: Brute Force, HashMap, Binary Search, Two Pointers of Problem 167. Two Sum II - Input Array Is Sorted.

Here shows 4 Approaches to slove this problem: Brute Force, HashMap, Binary Search, Two Pointers.

# Brute Force

It’s easy to use Brute Force to find the answer, however, the time complexity is $O(n^2)$, so the BF solution will Time Limit Exceeded!

## Analysis

• Time Complexity: $O(n^2)$.
• Space Complexity: $O(1)$.

# HashMap

We can use a extra $\texttt{HashMap}$ to record the element we traversalled.

## Analysis

• Time Complexity: $O(n)$.
• Space Complexity: $O(n)$.

# Binary Search

Since the array is already sorted, so we can use the binary search. In case of duplicated answer, we search only on the right of the left element.

## Analysis

• Time Complexity: $O(nlogn)$.
• Space Complexity: $O(1)$.

# Two Pointers

1. Let the two pointers point to the position of the first element and the position of the last element;
2. Each time the sum of the two elements pointed to by the two pointers is calculated and compared with the target value.
3. A unique solution is found if the sum of the two elements equals the target value.
4. If the sum of the two elements is less than the target, move the left pointer to the right one place; If the sum of the two elements is greater than the target, move the right pointer to the left by one.
5. Repeat until you find the answer.

## Analysis

• Time Complexity: $O(n)$.
• Space Complexity: $O(1)$.

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗