# 1. Two Sum

Reference: LeetCode
Difficulty: Easy

## Problem

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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)$ 18 ms
Space: $O(1)$

### Hash Table

Note: The order of the indices in the return array does not matter.

Reduce the look-up time from $O(N)$ to $O(1)$ by trading space for speed.

Two-pass: 2 ms

One-pass: 2 ms

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

Comment
Junhao Wang
a software engineering cat