顿搜
飞过闲红千叶，夕岸在哪
类目归类
哈希表——算法设计 · 篇七
08/16
一、最小包含字符窗口
GitHub地址：最小包含字符窗口.cpp
- ①、一个字符串能包含另一个字符串中所有子串的最小长度
1、使用两个指针，一个hash表，两个指针为了记录宽带，hash表为了记录是否存在
2、目标子串在两个指针之间出现了多少次，直到所有字符都出现在这段子串内
3、移动前面的指针，直到某一个子串出现在子串中一次
4、那么这个空间的长度就是当前最短的，这样遍历直到把所有字符串遍历结束
二、最长无重复字符子串
GitHub地址：最长无重复字符子串.cpp
- ①、最长没有重复字符的子串
1、假设所有的字符都是26个小写英文字符。以此建立hash表，hash表内记录着字符出现的位置
2、如果发现当前字符在以前遍历过的字符串中已经存在，那么从上次出现这个字符的位置的下一个字符重新遍历
三、直线上最多的点的个数
GitHub地址：直线上最多的点的个数.cpp
- ①、 共线最多的点的个数
1、可以看所有两点能够构造的直线的斜率，根据斜率来判断共线的点的个数。
2、这样斜率和该斜率上点的个数就构成了一个键值对，可以使用hash表来存储
