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
这一题完全可以用Two Sum中的解法来做，但是因为这里输入是排序过的数组，可以用更高效的算法。
Loop with Binary Search
O(nlogn) time, O(1) space
Two Pointers
O(n) time, O(1) space
即用numbers[low] + numbers[high]和target比较大小，来决定是low向右移，还是high向左移动。
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[2];
for (int i = 0; i < numbers.length; i++) {
int idx = binarySearch(numbers, target - numbers[i], i + 1, numbers.length - 1);
if (idx > 0) {
ans[0] = i + 1;
ans[1] = 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};
}
}