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

publicint[] 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) { returnnewint[] { i + 1, j + 1 }; // index starts from 1 } } } thrownew 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

publicint[] 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; returnnewint[] { i + 1, j + 1 }; } } thrownew IllegalArgumentException(); }

One-Pass:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

publicint[] 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 returnnewint[] { j + 1, i + 1 }; // notice the order } map.put(nums[i], i); } thrownew IllegalArgumentException(); }

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

Binary Search

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

publicint[] 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 returnnewint[] { i + 1, result + 1 }; } } thrownew IllegalArgumentException(); }

privateintbinarySearch(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 publicint[] 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) { returnnewint[] { i + 1, j + 1 }; } elseif (sum < target) { ++i; } else { // sum > target --j; } } thrownew IllegalArgumentException(); }