算法刷题

解法一：双重 DFS（外层 dfs 枚举起点，内层 findTarget 沿路径累计 sum）

解法二：前缀和 + 哈希表，dfs 一次遍历记录 s，命中 cnt[s-target] 即路径，回溯撤销

两种 DFS：递归子问题（左右深度+1 取大）/ 全局变量比较 max

DFS 递归中序遍历（左→根→右），带 ACM 模式建树 main

哈希表 + 双向链表 O(1)，头尾哨兵节点，get/put 移到头部

链表归并排序：快慢指针找中点拆两半，分治排序后 merge，注意 fast 起点快一个取左中点

最小堆：k 条链表头入堆，循环取堆顶接虚拟头，取出后把该链表下一个节点再入堆

哈希表 old_to_new 第一遍复制节点，第二遍连 next/random 指针

虚拟头节点 + 每 k 个一组局部反转，不足 k 个直接返回

先遍历算长度，虚拟头节点走到 size-n 位置删除；dummy 处理删头节点的情况

虚拟头节点 + 三指针 prev/first/second 两两交换相邻节点，注意奇数节点时的终止条件

链表逐位相加，carry 进位，注意最高位的进位

虚拟头节点 + 双指针归并；递归写法更简洁

快慢指针判环：slow 走一步 fast 走两步，相遇即有环；也可用哈希集合记录访问过的节点

判环后找入口：相遇点与头节点同步各走一步，再次相遇即环入口；需理解相遇点到入口的距离关系

迭代三指针反转：prev/cur/nex 逐个翻转指向

两种写法：递归回溯前后比较 / 快慢指针找中点+反转后半段比较，注意奇偶中点差异

哈希集合存 A 节点再遍历 B 找首个命中；双指针法可 O(1) 空间

用首行首列做标记位，O(1) 额外空间

按上下左右四条边走，走过的移除，每轮访问四条边界

原地旋转，先水平翻转再沿主对角线翻转，等价于 90° 顺时针

从右上角开始，比 target 大左移，比 target 大下移，O(m+n)

动态规划，pre = max(pre + x, x)，pre 表示以当前数结尾的最大和

排序 + 贪心，按左端点排序后遍历，重叠就更新右端点

三次反转：整体反转 + 前 k 反转 + 后 n-k 反转，注意 k %= n

左右乘积数组 L[i]*R[i]，空间可优化到 O(1)

原地哈希：把 <=0 的数改成 n+1，再对 [1,n] 用负号打标记，第一个正数位置 i+1 即答案

前缀和数组 s[i+1]=s[i]+nums[i]，查询 O(1)：s[right+1]-s[left]

前缀和 + 哈希表，统计 s[j]-k 出现次数

滑动窗口，r 扩张找可行解，l 收缩优化，注意 size() 无符号数陷阱

单调队列（双端队列），队头存当前窗口最大值

排序+双指针，注意去重

双指针左右夹逼，lmax 和 rmax 取较小的一边累计

双指针从两端向中间收敛，每次移动短板

快慢指针，慢指针左侧都是非零数

哈希表一次遍历 O(n)，注意 unordered_map 用法

对每个字符串排序作为 key，哈希表分组

哈希表存端点，只从连续序列起点开始计数 O(n)