哈希表-两数之和，最优解

51 阅读 0 评论 34 点赞

我是靠谱客的博主壮观睫毛，最近开发中收集的这篇文章主要介绍哈希表-两数之和，最优解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

思路：注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。
使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N)O(N)O(N) 降低到 O(1)O(1)O(1)。
这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

hash = dict()
for i, num in enumerate(nums):
if target - num in hashtable:#如果先前存的值，满足当下值+等于目标值，找出原来存的值的下标
return [hashtable[target - num], i]
hashtable[nums[i]] = i#键值对改变一下位置
return []