题目描述
给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。
说明:
返回的下标值(index1 和 index2)不是从零开始的。
你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。
样例
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
算法2
(双指针) $O(n)$
今天刚学习了双指针的模板,来练一下手,对于排序的数组,可以使用双指针来压缩搜索空间,起点分别设置在原数组两端,当l右移动可以时候,numbers[i]+numsbers[j]变大,r左移时候,和减少,不停的调整知道找到,l,r由于下标从1开始,l,r需要+1
C++ 代码
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int n=numbers.size();
for(int i=0,j=n-1;i<j;i++){
while(numbers[i]+numbers[j]>target) j--;
if(numbers[i]+numbers[j]==target)
return vector<int>({i+1,j+1});
}
return vector<int>({});
}
};
这么写可以得到结果,但是不够规范,对于要返回的值最好放在一个变量里面,变量j,i可读性不强,换成l,r
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
vector<int> res;
int n=numbers.size();
for(int l=0,r=n-1;l<r;l++){
while(numbers[l]+numbers[r]>target) r--;
if(numbers[l]+numbers[r]==target) {
res.push_back(l+1),res.push_back(r+1);
return res;
}
}
return res;
}
};