167. 两数之和 II - 输入有序数组

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

解法一：双指针

与1.两数之和 不同之处在于数组有序，因此不需要设哈希map，用左右两个指针，初始指向0和n-1，计算两数之和，若大于target，则右指针左移，若小于则左指针右移，直到找到target（题目假设一定有解），虽然复杂度和哈希map方法都是O（n），但是双指针法比一次遍历快一倍。

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n = len(numbers)
        if n < 2:
            return []
        left, right = 0, n-1
        while left < right:
            if numbers[left] + numbers[right] == target:
                return [left+1, right+1]
            elif  numbers[left] + numbers[right] > target:
                right -= 1
            else:
                left += 1