题目描述

 

示例

 

 思路分析

用双重for循环会超时，可以考虑使用双指针：i从0开始，j从numbers.size()-1开始，用一个while循环。

每次求出 numbers[i] + numbers[j] 的值，与target进行比较。如果相等则输出，较小则移动左指针(因为是非递减序列)，较大则移动右指针。

直到左指针等于右指针为止。

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> a;
        int i = 0,j = numbers.size()-1;//双指针法
        while(i<j){ //左指针等于右指针时，停止
            int sum = numbers[i]+numbers[j];
            if(sum==target){
                a.push_back(i+1);
                a.push_back(j+1);
                return a;
            }else if(sum<target){ //较小，移动左指针
                i++;
            }else{  //较大，移动右指针
                j--;
            }
        }
        return a;
    }
};