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:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Analysis

Brute-Force

1
2
3
4
5
6
7
8
9
10
11
12
public int[] twoSum(int[] nums, int target) {
// Assume nums is not null
int n = nums.length;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) { // j = i + 1 since we cannot use the same element twice
if (nums[i] + nums[j] == target) {
return new int[] { i, j };
}
}
}
throw new IllegalArgumentException("No two-sum solution");
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int[] twoSum(int[] nums, int target) {
// Assume nums is not null
int n = nums.length;
Map<Integer, Integer> map = new HashMap<>(); // <val, idx>
for (int i = 0; i < n; ++i) {
map.put(nums[i], i);
}
for (int i = 0; i < n; ++i) {
int val = target - nums[i];
if (map.containsKey(val) && map.get(val) != i) {
return new int[] { map.get(val), i };
}
}
throw new IllegalArgumentException("No two sum solution");
}

One-pass: 2 ms

1
2
3
4
5
6
7
8
9
10
11
12
13
public int[] twoSum(int[] nums, int target) {
// Assume nums is not null
int n = nums.length;
Map<Integer, Integer> map = new HashMap<>(); // <val, idx>
for (int i = 0; i < n; ++i) {
int val = target - nums[i];
if (map.containsKey(val)) {
return new int[] { map.get(val), i };
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}

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


Comment