Two Sum II - Input array is sorted

Given an array of integers that is alreadysorted 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:

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

Analysis

O(nlogn) time, O(1) space

Two Pointers

O(n) time, O(1) space

Solution

Binary Search - (3ms, 25.38%)

class Solution {
public int[] twoSum(int[] numbers, int target) {
if (numbers == null || numbers.length == 0) {
return new int[]{-1, -1};
}
int[] ans = new int;
for (int i = 0; i < numbers.length; i++) {
int idx = binarySearch(numbers, target - numbers[i], i + 1, numbers.length - 1);
if (idx > 0) {
ans = i + 1;
ans = idx + 1;
return ans;
}
}
return ans;
}
private int binarySearch(int[] nums, int target, int left, int right) {
if (nums == null || nums.length == 0) {
return -1;
}
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (target == nums[mid]) {
return mid;
} else if (target > nums[mid]) {
left = mid;
} else {
right = mid;
}
}
if (nums[left] == target) {
return left;
} else if (nums[right] == target) {
return right;
}
return -1;
}
}

Two Pointers - (1ms, 76.02%)

class Solution {
public int[] twoSum(int[] numbers, int target) {
int low = 0, high = numbers.length - 1;

while (low < high) {
int sum = numbers[low] + numbers[high];
if (sum == target)
return new int[]{low + 1, high + 1};
else if (sum < target)
++low;
else
--high;
}
return new int[]{-1, -1};
}
}