Two Sum, Sorted

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted

给定一个有序数组a, 一个数 T，问数组 a 中是否存在两个数之和等于 T，如果有则返回这两个数的（下标+1）

双指针方法

在排好顺序的数组中，

• 我们可以先求第一个数，即最小的数，和最后一个数，即最大的数他们的和，如果其和小于 target，则说明要把两个加数增大，而最后一个数已经是最大的，因此可以把第一个数增大，试试看第二个数与最后一个数的和
• 如果第一个数和最后一个数的和大于target，则说明这两个加数至少有一个数大了，因此需要将它们缩小，而第一个数已经是最小的了，因此只能把最后面一个数换成倒数第二个数，再加和进行比较

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

提交结果：

Runtime: 4 ms, faster than 96.10% of C++ online submissions for Two Sum II - Input array is sorted.
Memory Usage: 8.6 MB, less than 100.00% of C++ online submissions for Two Sum II - Input array is sorted.