LeetCode167: Sum of two numbers in sorted array

难度：simple
本题同时也是《剑指offer 专项突击》的第6题【数组专题】.

problem

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

给定一个已按照 升序排列 的整数数组 numbers ,请你从数组中找出两个数满足相加之和等于目标数 target .
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值.numbers 的下标 从 0 开始计数 ,所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length .
假设数组中存在且只存在一对符合条件的数字,同时一个数字不能使用两次.

类似的题

leetcode 1 号算法题：两数之和
leetcode 167 号算法题：两数之和Ⅱ - 输入有序数组
leetcode 170 号算法题：两数之和Ⅲ - 数据结构设计
leetcode 653 号算法题：两数之和Ⅳ - 输入 BST
leetcode 15 号算法题：三数之和
leetcode 18 号算法题：四数之和

哈希表

存 值-ID 对, save and find.

双指针

Double pointers for sorted arrays start at both ends.Move in the direction of the small,Move in the direction of the larger.

完整代码

class Solution:
    def twoSum(self, numbers, target: int):
        # hash 表： 值-ID
        # dic ={}
        # for i in range(len(numbers)):
        # if target - numbers[i] in dic:
        # return [dic[target-numbers[i]], i]
        # dic[numbers[i]] = i

        # 双指针
        i = 0
        j = len(numbers)-1
        while i <= j:
            if numbers[i]+numbers[j] == target:
                return [i+1,j+1]
            elif numbers[i]+ numbers[j]<target:
                i +=1
            else:
                j-=1