167. Two Sum II - Input array is sorted
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.
Input: numbers=[2, 7, 11, 15], target=9
Output: [1,2]
之前介绍过Two Sum系列问题的解法，这道题只是多出了一个数组已经排好序的条件，所以之前的思路可以继续使用：
- hash-table
- two pointers
第一种方法使用hash Table，确定一个数，然后在数组中寻找target与该数的差值即可，代码如下:
/*solution 1 ,use hash-table 8ms*/
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
if(numbers.empty())
return {};
unordered_map<int,int> hash;
vector<int> res(2,0);
for(int i=0;i<numbers.size();i++){
int tmp=target-numbers[i];
if(hash.find(tmp)!=hash.end()){
res[0]=hash[tmp]+1;
res[1]=i+1;
}
else
hash[numbers[i]]=i;
}
return res;
}
};
第二种方法使用双指针，一个指首部一个指尾部，若两个被指向的值的和大于target，则右指针左移，否则左指针右移，代码如下:
/*solution2 two pointers 8ms*/
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int left = 0, right = numbers.size() - 1;
vector<int> res;
while(left < right){
long long val = numbers[left] + numbers[right];
if(val == target){
res.push_back(left + 1);
res.push_back(right + 1);
return res;
}
else if(val < target)
left++;
else
right--;
}
return res;
}
};