1. 167

two-sum-ii-input-array-is-sorted/

2. 算法

• 双指针:O(n)

我们只需要两个指针，一个指向开头，一个指向末尾，然后向中间遍历，如果指向的两个数相加正好等于target的话，直接返回两个指针的位置即可，若小于target，左指针右移一位，若大于target，右指针左移一位，以此类推直至两个指针相遇停止，参见代码如下：

3. 代码

// O(n)
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int n=numbers.size();
        vector<int>  result;
        if(n<=1)  return result;
        int start=0,end=n-1;
        while(start<end){
            if(numbers[start]+numbers[end]<target)
                ++start;
            else if(numbers[start]+numbers[end]>target)
                --end;
            else{
                result.push_back(start+1);
                result.push_back(end+1);
                break;
            }
        }
        return result;
    }
};