167. 两数之和 II - 输入有序数组【简单】

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

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

说明:

返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

思路

方法一：

循环遍历有序数组，累加使得 num1 + num2 = target

耗时长，时间复杂度高，已超时

方法二：

hash，python中使用字典处理，遍历存储 target - num1 的值为字典 d 的 key，index 为字典 d 的 value，如果 num2 在字典 d 中，即 target - num1 = num2，则返回 num1 和 num2 的 index 值，如果不在则继续遍历。

方法三：

双指针，左右指针left、right初始化对应有序数组的首尾两个值 num[0] 和num[-1]，开始遍历，若 num[left] + num[right] < target，则 left+1，继续遍历，若num[left] + num[right] > target，则 right-1，继续遍历，直到 num[left] + num[right] = target，返回对应index值。

代码

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # 方法一：循环遍历，时间复杂度高 
        res = []
        for i in range(len(numbers)-1):
            if numbers[i] <= target:
                for j in range(i+1, len(numbers)):
                    if numbers[i] + numbers[j] == target:
                        res.append(i+1)
                        res.append(j+1)
        return res
        
        # 方法二：hash  164 ms	14.4 MB
        d = {}
        for i in range(len(numbers)):
            if numbers[i] in d:
                return [d[numbers[i]], i+1]
            else:
                d[target - numbers[i]] = i+1
                continue
        
        # 方法三：双指针   108 ms	14.4 MB
        l = 0
        r = len(numbers)-1
        while l < r:
            if numbers[l] + numbers[r] == target:
                return [l+1,r+1]
            elif numbers[l] + numbers[r] < target:
                l += 1
            else:
                r -= 1