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. Please note that 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.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
翻译:给你一个以递增方式已经排序好的整数数组,查找相加为特定值的两个数。
注意:第一个索引必须小于第二个索引。
TWO-SUM的简单变式。后面还有一堆2333
解法:效率是O(NlogN),使用双指针,一个指向头p1,一个指向尾p2。 遵循的策略是 如果p1+p2的值小于target,那么显然的所有以P1为开头的配对都是不可能的,因为以P1为开头的值最大就是P1+P2,而它是小于target的,在这种情况下我们需要将p1指向下一个元素,取寻找下一个可能的配对。如果p1+p2的值大于target,那么显然的所有以P2为结尾的配对都是不可能的,因为以P2为配对的最小值就是P1+P2,所以为了找到可能的值,必须将P2指向前一个元素。如果P1+P2等于target 那么从题意来看我们已经找到目标了,直接break。
class Solution {
public int[] twoSum(int[] numbers, int target) {
int[] result = new int[2];
int pos1 = 0 ;
int pos2 = numbers.length-1;
while(pos1<pos2)
// 注意等号是不可取的,要保证每个元素不可以使用两次
{
if(numbers[pos1]+numbers[pos2]==target)
{
result[0]=pos1+1;
result[1]=pos2+1;
break;
}
else if (numbers[pos1]+numbers[pos2]<target)
{
pos1++;
}
else
{
pos2--;
}
}
return result ;
}
}