Day 9 ：什么是哈希表？

1 Day 8 总结

Day 8 是 LeetCode 中非常经典的一道题目：两数之和。

题目描述如下：

大家注意审题，确定输入是什么，输出又是什么，假定又是什么。

输入：待寻找的列表 nums, 两数之和 target

输出：有且仅有满足要求的一对整数的下标

假定：一定存在，且仅有一个答案

题目分析：两个数之和等于 target, 首先标记所有遍历过的数，如果 target 减去当前被遍历到的值 e 后，即 target-e 被标记过，则找到答案。

判断值是否在某个容器中，做到 O(1) 时间复杂度的便是最常用的散列表，对应 Python 中的字典。就本题而言，键为标记元素值，字典值为数组下标，所以更加确定使用字典这个数据结构。

代码 ：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d = {}
        for i,e in enumerate(nums):
            if target -e in d:
                return [i,d.get(target-e)]
            d[e] = i 

以上是比较高效的解法之一。

从星球中星友提交的代码看，有一些星友的代码就是上面的实现思路。

但是，也有一些星友的代码是这样的，解并没有达到时间复杂度为 O(n)，大家不妨参考并回头检查下自己写的。

不高效解1：index 时间复杂度O(n)

index 复杂度为 O(n), 所以实际时间复杂度为 O(n^2)，尽管表面上看只有一个 for 循环。

不高效解2：两层 for

下面代码两层 for，空间复杂度虽然为 O(1)，但是时间复杂度为 O(n^2)。所以需要找到牺牲空间换取时间的方法。

以上使用散列表牺牲空间，但是换取时间，实际中能找到节省时间的解往往更有价值。

2 Day 9 打卡题：什么是哈希表？

明天的打卡题，我们就来学习最重要的数据结构之一：散列表或哈希表，那么什么是哈希表呢？哈希表怎么做到 O(1) 时间复杂度找到某个元素的呢？

提供参考资料如下，大家可参考。

《我的第一本算法数》.pdf ，星球内提供电子版，仅供个人学习用，严禁用于其他用途。

图片1：哈希表的基本用途

图2：哈希表的查找规则：

图3：哈希表常遇到键冲突问题：

图 4 ：解决方法：

星球内的星友直接学习本书的 1-6 解即可。然后把打卡题：什么是哈希表？哈希表怎么做到 O(1) 时间复杂度找到某个元素？