Two Sum II – Input array is sorted
two sum问题, 只是这次的input是sorted. 这题因为肯定有答案, 所以用二叉搜索.
class Solution {
public int[] twoSum(int[] numbers, int target) {
for(int i = 0; i < numbers.length; i++) {
int t = bs(numbers, i+1, numbers.length - 1, target - numbers[i]);
if(t != -1)
return new int[]{i+1, t+1};
}
return null;
}
private int bs(int[] nums, int start, int end, int n) {
while(start <= end) {
int mid = start + (end - start) / 2;
if(nums[mid] == n)
return mid;
else if(nums[mid] > n)
end = mid - 1;
else
start = mid + 1;
}
return -1;
}
}