LeetCode 167 Two Sum II - Input array is sorted（左右指针）

题目链接：点击这里

一个最直观的想法是，使用二重循环枚举序列中的整数，判断它们的和是否为 $target$target，如果是，输出方案；如果不是，则继续枚举。

显然，这种做法的时间复杂度为O(n²)，对 $n$n 在 $10^5$105 的规模时是不可承受的。

【two pointers】

初始化：令下标 $i$i 的初值为 $0$0，下标 $j$j 的初值为 $n-1$n−1，即令 $i$i、$j$j 分别指向第一个元素和最后一个元素。

two pointers 思想充分利用了序列递增的性质，变量 $i$i 只有递增操作、变量 $j$j 只有递减操作，$i$i 和 $j$j 的操作次数最多为 $n$n 次，时间复杂度为 $O(n)$O(n)。

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int i = 0, j = numbers.size()-1;
        while(i<j)
        {
            int sum = numbers[i]+numbers[j];
            if(sum==target)
                return {i+1,j+1};	//have exactly one solution
            else if(sum<target)
                i++;
            else
                j--;
        }
        return {-1,-1};
    }
};