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)$