两数之和等于目标数【数组专题】

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:

返回的下标值（index1 和 index2）不是从零开始的。

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例:

输入: numbers = [2, 7, 11, 15], target = 9

输出: [1,2]

解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

class Solution {

public:

    vector<int> twoSum(vector<int>& numbers, int target) {

// 初始思路：用双指针，一个快，一个慢，先固定慢的一个，然后移动快指针。

     该思路存在的问题：

int slow = 0 ;

     for(int fast = 1 ; fast < numbers.size() ; ++fast) {

         if(numbers[slow] + numbers[fast] == target) {

           return {++slow , ++ fast};

         }

     }

     return { -1 , -1};

并且该解法并未判断左右指针的大小

     // 改进思路：首尾各设一个指针，条件为左边的指针下标要小于右边，然后判断加起来的值和目标值的比较结果。如果大了，把后面的往前移一位，如果小了，把前面的往前移一位。刚好相等的话就返回左+1，右加1.

int left = 0 , right = numbers.size() - 1;

    while(left < right) {      

         int sum = numbers[left] + numbers[right] ;

         if(sum == target) {

           return {++left , ++right};

         }

         else if(sum < target) {

           ++left;

         }

         else

           --right;

     }

     return { -1 , -1};