问题描述
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:
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.
解决思路
因为数组本身是有序的，所以设置头指针和尾指针。如果两数之和大于target,则尾指针向左移，若两数之和小于target则头指针向右移。
问题解惑
一开始我还想这题和Pro1 Two Sum有啥区别，就把Pro1的代码拿来跑了一下，发现可以通过但效率太低了，又仔细看了一下，发现Pro1的数组无序，Pro167的数组是升序的，所以处理手法就会不同，效率自然也不同了。
代码
package leetcode;
import java.util.HashMap;
public class TwoSumII_InputArrayisSorted {
public int[] twoSum(int[] numbers, int target) {
//判断边界条件
if (numbers.length < 2 || numbers == null){
return new int[]{-1, -1};
}
int begin = 0, end = numbers.length - 1;
int[] res = new int[]{-1,-1};
while (begin < end){
if (target == numbers[begin] + numbers[end]){
break;
}
if (target > numbers[begin] + numbers[end]){
begin++;
}else {
end--;
}
}
res[0] = begin + 1;
res[1] = end + 1;
return res;
}
}
