给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
最简单的思路就是用两层for循环，寻找数组中两个数的和等于targer
vector<int> twoSum(vector<int>& numbers, int target) {
for(int i=0;i<numbers.size();i++)
{
for(int j=i+1;j<numbers.size();j++)
{
if(numbers[j]>target &&target>0)
{
break;
}
if(numbers[i]+numbers[j]==target)
{
return {i+1,j+1};
}
}
}
return {0,0};
}
但是这样效率很低，执行时间268ms，内存消耗9.6MB
另一个思路，看到是从数组中寻找两个位置的数字，就不由得想到可以用双指针来解决。
令两个指针分别从数组的两头出发，相当于将最大值和最小值相加，左边的指针向右移动会使和增大，右边的指针向左移动会使和减小，因此根据两个位置和的情况改变指针的位置直到找到结果。
vector<int> twoSum(vector<int>& numbers, int target) {
if(numbers.empty())
{
return {0,0};
}
int first=0;
int last=numbers.size()-1;
while(first<last)
{
if(numbers[first]+numbers[last]==target)
{
return {first+1,last+1};
}
else if(numbers[first]+numbers[last]>target)
{
last--;
}
else if(numbers[first]+numbers[last]<target)
{
first++;
}
}
return {0,0};
}
使用双指针这种方法时间复杂度就只有O(n)，在leetcode上提交致性用时4ms，内存消耗9.6MB，相比于原来的方法时间减少了很多