题意:给你一个排好升序的数组和一个目标值,让你找出数组中的两个值使得他们的和等于目标值,返回这两个值对应的下标。
思路:如果两两组合来求解的话时间复杂度为O(n*n)。由于数组是升序的,所以可以从两侧同时遍历,根据两侧值的大小来缩小范围,只用了O(n)的时间
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int l = 0,r = numbers.size()-1;
while(1)
{
if(numbers[l]+numbers[r]==target)
{
vector<int> res{l+1,r+1};
return res;
}
else
{
if(numbers[l]+numbers[r]>target)
r--;
else
l++;
}
}
}
};