hot100思路总结
Hot100
哈希
- 两数之和
遍历同时用map记录已经遍历过的元素
- 字母异位词分组
单词字典排序作为key，原单词作为value，最后取出map中的value作为切片
- 最长连续序列
map记录每个数，遍历map，从最小的数开始找记录长度
双指针
- 移动零
同向双指针，一个遍历元素，一个标记非零元素
- 盛最多水的容器
相向双指针，接水问题，高度由较短的一边决定
- 三数之和
排序，固定一个数后还是两数之和，相向双指针，关键是注意去重
- 接雨水
一个位置一个桶，一个桶两个边，桶盛水量由“前后缀的较小方决定”。每次更新左右其中一个桶，相向双指针
滑动窗口
- 无重复字符的最长子串（耐考王）
map记录子串元素出现次数，同向双指针->只出现一次
- 找到字符串中所有字母异位词
map记录目标元素出现次数，同向双指针->和目标元素出现次数一致
子串
- 和为 K 的子数组
子数组和问题->前缀和的差，用map记录前缀出现次数
普通数组
- 最大子数组和
子树数组和问题->前缀和，求最大，维护一个最小前缀和即可
- 合并区间
关键：go语言中的自定义排序api
- 轮转数组
反转整体，分别反转前后两部分
- 除了自身以外数组的乘积
维护前缀积和后缀积，然乘在一起
矩阵
- 矩阵置零
不考
- 螺旋矩阵
不考
- 旋转图像
纯背：矩阵转置->行反转
- 搜索二维矩阵 II
从右上角开始搜
链表
- 相交链表
双指针同时遍历，空指针就跑到另一个链头去
- 反转链表
空pre开始，返回pre结束
- 回文链表
1.找到链表中间；2.反转后半段；3.一个个节点遍历对比；
- 环形链表
快慢指针
- 环形链表 II
纯背：找到相交的位置，然后头节点和慢指针一起出发直至相遇
- 合并两个有序链表
太简单，没技巧
- 两数相加
定义一个进位计数变量count，取数取模，进位除十
- 删除链表的倒数第 N 个结点
快慢指针，注意从空节点开始
- 两两交换链表中的节点
纯背，没技巧
回溯
- 全排列
全排列问题需要每次从头遍历，且标记已经访问的元素
（77. 组合）
和排列问题区别在于顺序不重要，所以不用从头递归，且本题边界条件是指定长度
- 子集
空集也是子集，所以每一层调用都要收集结果
- 电话号码的字母组合
和77.组合差不多，不过每层的选择空间不是同一个空间
- 组合总和
引入状态变量，所以也要回溯，因为可以重复添加，所以从当前位置继续递归
- 括号生成
非边界两种情况，左括号不满可以添加左括号，右括号小于左括号可以添加右括号
- 单词搜索
边界：单词搜索完成，非边界：坐标越界、已经搜过（map标记）、不是单词
- 分割回文串
非边界：切一个子串s[i: j+1]判断是不是回文串
- N 皇后
背就完了，关键性质：对角线坐标性质->左上右下（坐标差相同）、右上左下（坐标和相态）