题型归纳与重要模版

题型归纳

子数组/子字符串 -> 滑动窗口算法

和为 xxx 的子数组 -> 前缀和与哈希表的结合使用

带权重的随机选择算法 -> 前缀和与二分搜索

两个字符串求子序列 -> 动态规划（用两个指针 i 和 j 分别在两个字符串上移动）

O(1) 时间对整个区间的元素进行加减 -> 差分数组

数据结构复制 -> 一个哈希表 + 两次遍历

二叉树 -> 递归 -> 「遍历」和「分解问题」两种思维模式

二叉树的构建 -> 先构造根节点，然后构建左右子树

排列、组合、子集 -> 回溯

岛屿问题 -> DFS

单调关系 -> 二分搜索

括号匹配 -> 栈

两个字符串的动态规划问题 -> 一般都是用两个指针i, j分别指向两个字符串的头部或尾部，然后尝试写状态转移方程。

重要模版

• 滑动窗口模版
• 二分搜索模版
• 前缀和模版
• 二叉树的 DFS 和 BFS 遍历模版
• 图的 DFS 和 BFS 遍历模版
• 构建图的模版（邻接表）