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

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

说明:

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

示例:

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

题目思路：

     如果直接暴力解决，时间复杂度为（O（n**2）），很明显这种方法会pass。

     那么如果给定的数组是有序的会不会降低难度呢？如果是有序的数组，那么我们可以用首尾相加来处理，如果比target大，则将尾数左移，如果小了首尾右移，直到两个数相加刚好等于target, 这种方法的时间复杂度为（O（nlogn）。

     最后一种方法。在python里面有一个dict的和C++ 的map功能一样。首先，我们建立一个字典，d = {}，字典的key是数组的值number，value是相应的位置， 然后只要满足 number 和 target - number都在字典里面则找到答案。这种方法的时间复杂度是（O（n））。

class Solution(object):
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
d = {}
# d is a dict to map the value of numbers and the index in numbers
size = 0
while size < len(numbers):
if not numbers[size] in d:
d[numbers[size]] = size + 1
if target - numbers[size] in d:
if d[target-numbers[size]] < size + 1:
answer = [d[target - numbers[size]] , size + 1]
return answer
size = size + 1

最后

以上就是踏实泥猴桃为你收集整理的leetcode 两数之和 II - 输入有序数组 python题目思路：的全部内容，希望文章能够帮你解决leetcode 两数之和 II - 输入有序数组 python题目思路：所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。