一、题目描述
给出一个整数数组，请在数组中找出两个加起来等于目标值的数， 你给出的函数twoSum需要返回这两个数字的下标（index1，index2），需要满足 index1 小于index2.。注意：下标是从1开始的。
假设给出的数组中只存在唯一解
例如： 给出的数组为 {20, 70, 110, 150},目标值为90
输出 index1=1, index2=2
二、解题思路
（一）暴力解法：使用两个循环，定义两个数组下标索引(不建议)
解题思路：
1、第一层循环应从0到n-2位置（n为数组长度），即不需要遍历到数组最后一个元素；
2、第二层循环应将第一层循环变量作为起点，遍历至数组最后一个元素。
3、下标从1开始，因此在保存结果时，要注意加1。
class Solution:
def twoSum(self , numbers , target ):
# write code here
for i in range(len(numbers)):
for j in range(i+1,len(numbers)):
if numbers[i] + numbers[j] == target:
return[i+1, j+1]
（二）哈希表:时间复杂度可以进一步优化至O(N)。
哈希表的思想为「以空间换时间」，这是由于哈希表保存了键值对，其「查找」复杂度为O(1)。
解题思路：
定义哈希表hashmap，其存放的键值对为<取值，下标>。
从开始处遍历数组，对于第i个位置，在哈希表中寻找target-nums[i]是否存在，若存在，将两个下标放入数组中返回；若不存在，将其添加至表中，继续遍历。
图示如下：
动画演示如下：注：在将结果保存至数组中时，无需判断二者下标大小：当所遍历到的位置符合题目要求时，说明哈希表中已经存在待查找的另一元素，因此「已存在于表中的元素的下标」一定小于「当前位置元素的下标」
使用Map来降低时间复杂度，遍历数组，如果没有 （target – 当前值） 就将当前数字存入哈希表，如果有，返回该数字下标即可。
class Solution:
def twoSum(self , numbers , target ):
# write code here
map1 = {}
for i in range(len(numbers)):
if target - numbers[i] in map1:
return [map1[target - numbers[i]]+1, i+1]
else:
map1[numbers[i]] = i
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/99773.html
