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
翻譯：給你一個(gè)以遞增方式已經(jīng)排序好的整數(shù)數(shù)組距糖，查找相加為特定值的兩個(gè)數(shù)碴开。
注意：第一個(gè)索引必須小于第二個(gè)索引灌灾。
TWO-SUM的簡(jiǎn)單變式览爵。后面還有一堆2333
解法：效率是O(NlogN）,使用雙指針彪腔，一個(gè)指向頭p1森枪，一個(gè)指向尾p2辽社。 遵循的策略是 如果p1+p2的值小于target喘先，那么顯然的所有以P1為開頭的配對(duì)都是不可能的楷扬，因?yàn)橐訮1為開頭的值最大就是P1+P2解幽，而它是小于target的，在這種情況下我們需要將p1指向下一個(gè)元素烘苹，取尋找下一個(gè)可能的配對(duì)躲株。如果p1+p2的值大于target，那么顯然的所有以P2為結(jié)尾的配對(duì)都是不可能的镣衡，因?yàn)橐訮2為配對(duì)的最小值就是P1+P2,所以為了找到可能的值霜定，必須將P2指向前一個(gè)元素。如果P1+P2等于target 那么從題意來看我們已經(jīng)找到目標(biāo)了廊鸥，直接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)
// 注意等號(hào)是不可取的，要保證每個(gè)元素不可以使用兩次
{
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 ;
}
}
