LeetCode 167 Two Sum II
Q:
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.
Note:
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.
翻译君:一个有序数组，找到两个数和等于特定数的位置。
注意索引从1开始并且数组中的一个元素只能用一次。
比如 [1,2,3,4,4,9,56,90],target=8 返回[4,5]
1.最容易想到的解法-暴力解法
遍历数组两次，找到这两个数。解法简单但是没有用到数组有序这一特性。时间复杂度O(n^2)
太孬了，不采用......
2.逆转思维-二分查找法
想到数组有序就应该想到二分查找。
先确定一个数，就只需要找另外一个数就好了。利用二分查找target-i
时间复杂度O(nlogn),相比暴力解法快了很多，不是一个量级的了。
上代码
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
vector<int> result;
for(int i=0;i<numbers.size();i++){
int second=target-numbers[i];
//二分查找法找另外一个数
int l=i+1;
int r=numbers.size()-1;
while(l<=r){
int mid=l+(r-l)/2;
if(second<numbers[mid])
r=mid-1;
else if(second>numbers[mid])
l=mid+1;
else{
result.push_back(i+1);
result.push_back(mid+1);
break;
}
}
if(result.size()==2) break;
}
//---
return result;
}
};
那还有没有其他更厉害的解法了呢？
能不能只遍历一次数组就可以找到这两个数？
3.对撞指针法
利用两个指针分别指向头尾，通过头尾数之和和目标数进行比较，前者大则尾指针左移，前者小则指针右移。充分利用了排好序数组这一特性。只需要O(n)的时间复杂度。代码也相当简洁。不信？上代码瞧瞧。
class Solution2{
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int l=0;
int r=numbers.size()-1;
//l不能大于r的原因：l==r指针相撞那么就可能会取到同一个数，这是不符合题意（一个元素不能用两次）
while(l<r){
if(numbers[l]+numbers[r]==target){
int res[2]={l+1,r+1};
return vector<int>(res,res+2);
}
else if(numbers[l]+numbers[r]>target)
r--;
else
l++;
}
}
};
运算结果只用了4ms，这才是酷酷的解法
