需掌握的清单

1. 双指针（Two Pointers）

1.1 滑动窗口（Sliding Window）

适用场景
求满足某一条件（和 ≥ target、不重复字符、包含所有字符）的连续子数组/子串，且数据具有单调性（如正整数）或窗口边界可单向推进。

思路要点
- 右指针 right 不断右移，扩大窗口，直到窗口首次满足条件（或触发收缩信号）。
- 然后内层 while 收缩左指针 left，尝试在满足条件的前提下缩小窗口，记录最优解。
- 窗口内状态通常用哈希表或变量维护（计数、和等）。

模板口诀

left = 0
for right in range(n):
    # 将 nums[right] 加入窗口，更新状态
    while 窗口需要收缩:
        # 更新答案（如果需要）
        # 移除 nums[left]，left += 1
    # 更新答案（或在此处更新）

推荐题目（二选一即可，时间紧优先做 209）
- 209. 长度最小的子数组 —— 纯和条件，最标准模板。
- 3. 无重复字符的最长子串 —— 哈希表维护字符出现次数，高频。

1.2 左右指针（对撞指针）

适用场景
在有序数组或可推理单调性的数组中，从两端向中间逼近，寻找满足特定关系的元素对（两数和、面积最大等）。

思路要点
- 初始化 left = 0, right = n-1。
- 根据当前状态决定移动哪一侧：若 nums[left] + nums[right] 过大则 right--，过小则 left++。
- 移动方向依据问题特性（如有序、高度限制）单向决定，不会回溯。

推荐题目
- 11. 盛最多水的容器 —— 移动较矮的柱子，贪心证明。
- 15. 三数之和 —— 先排序，固定一个数，再对撞双指针找另外两个，注意去重。

1.3 快慢指针（龟兔赛跑）

适用场景
链表或数组中的环路检测、寻找重复数、寻找中点等，通过步长差异（慢走1，快走2）来建立数学关系。

思路要点
- 慢指针 slow 每次走一步，快指针 fast 每次走两步。
- 若存在环，则 fast 最终会追上 slow；若无环，fast 先到达终点。
- 对于找环入口，在第一次相遇后，将 slow 重置到头结点，两者再以相同速度（每次一步）前进，再次相遇点即为环入口。

推荐题目
- 142. 环形链表 II —— 必会，数学推导可提前背下。

2. 哈希表 + 前缀和（Hash + Prefix Sum）

适用场景
需要快速统计子数组和等于 k 的个数，或者对连续区间进行计数时，利用 前缀和 + 哈希表 将 O(n²) 降为 O(n)。

思路要点
- 维护一个变量 cur_sum 记录当前位置的前缀和。
- 哈希表 map 存储 “前缀和 → 出现次数”，初始化 map[0] = 1。
- 对于每个位置 i，计算 cur_sum - target，若该差值存在于 map 中，则累加其出现次数。
- 然后将当前 cur_sum 计入 map。

推荐题目
- 560. 和为 K 的子数组 —— 经典前缀和+哈希，注意是子数组个数，不是长度。

3. 单调栈（Monotonic Stack）

适用场景
需要寻找数组中下一个更大/更小元素，或计算温度、柱状图面积等问题。保持栈内元素单调递增或递减，利用栈消除冗余比较。

思路要点
- 遍历数组时，对于当前元素，若栈顶元素小于（或大于）当前元素，则栈顶元素的下一个更大（更小）元素就是当前元素，弹出并记录。
- 否则将当前元素下标入栈（或元素本身）。
- 通常用栈存下标，方便计算距离。

推荐题目
- 739. 每日温度 —— 求下一个更高温度的天数差，单调栈标准板子。

4. 二叉树（Binary Tree）

4.1 层序遍历（BFS）

适用场景
按层输出节点值、求最大深度（也可DFS）、判断是否对称等。测开常考手写 BFS。

思路要点
- 使用队列 deque，初始放入根节点。
- 每层先记录当前队列长度 level_size，然后循环弹出 level_size 次，将子节点入队。
- 每层收集的值放入一个列表，最终返回所有层列表。

推荐题目
- 102. 二叉树的层序遍历 —— 纯 BFS，必练。

4.2 中序遍历（BST 性质）

适用场景
验证二叉搜索树、查找第 K 小元素等，利用 BST 中序遍历结果为严格递增序列的特性。

思路要点
- 递归或迭代（栈）进行中序遍历（左-根-右）。
- 验证时，维护一个前驱节点 pre，检查当前节点值是否 > pre，否则无效。
- 迭代写法可避免递归深度过大。

推荐题目
- 98. 验证二叉搜索树 —— 中等难度，注意节点值范围陷阱（要用 long 或 None）。

5. 二分查找（Binary Search）

适用场景
在有序（或部分有序）数组中查找特定元素或边界，时间复杂度 O(log n)。核心是排除一半。

思路要点
- 定义 left, right，循环条件 left <= right 或 left < right（视模板而定）。
- 计算 mid = left + (right - left) // 2 防止溢出。
- 根据 nums[mid] 与 target 的关系，调整左右边界。
- 对于旋转数组，需额外判断哪一侧是有序的，再决定搜索区间。

推荐题目
- 33. 搜索旋转排序数组 —— 经典中的经典，逻辑需仔细。
- 34. 在排序数组中查找元素的第一个和最后一个位置 —— 二分找左右边界，熟练后一通百通。

6. 链表（Linked List）

适用场景
链表操作常考反转、删除、合并，测开面试中必须能手写单链表相关基础操作。

思路要点
- 删除倒数第 N 个节点，可用快慢指针：快指针先走 N 步，然后快慢一起走，当快指针到末尾时，慢指针恰好指向待删节点的前驱。
- 注意加入哑结点（dummy）简化边界处理。

推荐题目
- 19. 删除链表的倒数第 N 个结点 —— 双指针一次遍历，边界需注意。

📌 刷题建议（时间紧急版）

优先级排序（按面试出现频率）：
滑动窗口（209/3） > 三数之和（15） > 环形链表（142） > 每日温度（739） > 层序遍历（102） > 二分查找旋转（33） > 和为K子数组（560）。
每道题先看 5 分钟思路，如果不会直接看题解，理解后手写一遍，然后默写第二遍。
每题控制在 20 分钟内完成（包括调试）。
测开加分项：写完后主动讲出测试用例设计（空输入、单元素、重复元素、大数等），这比纯算法更吸引面试官。

如果时间实在紧张，最少必须刷完：209、15、142、739、102 这五道，覆盖了最核心的几种思想。祝你顺利！有具体题目卡壳随时问我。 😊