打卡题目：leetcode第167题，两数之和Ⅱ-输入有序数组
    类似题目：1、15、18
    image.png

    【思路】

    1. 暴力解法：两轮for循环，遍历所有可能，时间复杂度太高。
    2. 双指针：只是两个指针i和j分别指向第一个元素和最后一个元素，不断比较nums[i]+nums[j]和target的大小，并移动指针。如果nums[i]+nums[j]>target，则i后移，使得两数和变大；如果nums[i]+nums[j]<target，则j前移，使得两数和变小。
    3. hash：遍历数组，判断target-nums[i]是否存在字典d中，存在则返回结果；不存在则将元素及位置存储在字典中，即d[nums[i]]=i。

    【代码】

    1. # 双指针
    2. class Solution:
    3.     def twoSum(self, numbers: List[list], target: int) -> List[int]:
    4.         l, r = 0, len(numbers)-1
    5.         while l < r:
    6.             # 刚好相等，退出
    7.             if numbers[l] + numbers[r] == target:
    8.                 break
    9.             # 和更大，r指针前移
    10.             elif numbers[l] + numbers[r] > target:
    11.                 r -= 1
    12.             # 和更小，l指针后移
    13.             else:
    14.                 l += 1
    15.         # 保证有结果，不用再判断是否满足条件
    16.         # 注意，本题返回的下标从1开始
    17.         return [l+1, r+1]
    1. # hash
    2. class Solution:
    3.     def twoSum(self, numbers: List[int], target: int) -> List[int]:
    4.         d = {}
    5.         for i, n in enumerate(numbers):
    6.             if target - n not in d:
    7.                 d[n] = i
    8.             else:
    9.                 # 注意，本题返回的下标从1开始
    10.                 return [d[target - n] + 1, i + 1]
    11.         # 保存有结果，可以不用再判断是否满足条件
    12.         return [-1, -1]