Reference: LeetCode
Difficulty: Easy

My Post: Java Solutions (Brute-Force, Hash Table, Binary Search, Two Pointers)

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:

1
2
3
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

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) { // cannot use the same twice
if (nums[i] + nums[j] == target) {
return new int[] { i + 1, j + 1 }; // index starts from 1
}
}
}
throw new IllegalArgumentException();
}

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

Hash Table

Two-Pass:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int[] twoSum(int[] nums, int target) {
// Assume nums is not null
int n = nums.length;
// set map
Map<Integer, Integer> map = new HashMap<>(); // <val, index>
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)) {
int j = map.get(val);
if (i == j) continue;
return new int[] { i + 1, j + 1 };
}
}
throw new IllegalArgumentException();
}

One-Pass:

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;
// set map
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; ++i) {
int val = target - nums[i];
if (map.containsKey(val)) {
int j = map.get(val); // j is always ahead of i
return new int[] { j + 1, i + 1 }; // notice the order
}
map.put(nums[i], i);
}
throw new IllegalArgumentException();
}

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public int[] twoSum(int[] nums, int target) {
// Assume nums is not null
int n = nums.length;
for (int i = 0; i < n; ++i) {
// binary search
int t = target - nums[i];
int lo = i + 1, hi = n - 1; // i + 1 instead of i
int result = binarySearch(nums, lo, hi, t);
if (result != -1) { // found
return new int[] { i + 1, result + 1 };
}
}
throw new IllegalArgumentException();
}

private int binarySearch(int[] nums, int lo, int hi, int t) {
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == t) return mid;
if (nums[mid] > t) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
return -1;
}

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

Two Pointers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 2  3  5  8  10, target = 11
public int[] twoSum(int[] nums, int target) {
// Assume nums is not null
int n = nums.length;
int i = 0, j = n - 1;

while (i < j) { // element is only used once.
int sum = nums[i] + nums[j];
if (sum == target) {
return new int[] { i + 1, j + 1 };
} else if (sum < target) {
++i;
} else { // sum > target
--j;
}
}
throw new IllegalArgumentException();
}

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


Comment