连着刷了两周机考题，这次更新到第14、15天的进度，正好碰到LeetCode 437和1208。这两道题放在一起很有意思：437是二叉树路径问题，考DFS里的前缀和统计与回溯恢复；1208是字符串替换问题，考滑动窗口的边界收缩。一个在树上，一个在数组上，表面风马牛不相及，但做完复盘下来，它俩其实共享同一套底层思维——把“连续一段的累计值”用前缀和或窗口的方式算清楚。这篇就当作这两天的刷题记录来写，把思路推导、完整代码、易错点和机考踩坑都整理出来，给同样在准备机考、刷到树和双指针这类题的朋友做个参考。如果你对437的前缀和思路和1208的滑动窗口模板还不熟，这篇可以直接当复习材料用。
1. 两道题在机考题型里的定位与考频
1.1 437属于“树路径类”高频题
437题名叫“路径总和III”，和112、113是同一个家族。112只需要判断是否存在一条从根到叶子的路径，和为targetSum；113要把所有满足条件的路径都打印出来；到了437，限制突然放宽：路径可以从任意节点开始，也可以在任意节点结束，只要保证方向是从父节点到子节点。这个放宽让112那种“从根往下做减法”的简单思路直接失效，因为路径的起点不再固定，终点也不再固定。
正因为难度跨了一档，437在面试和机考里出现频率很高，经常被当作“前缀和加哈希表”的测试点。面试官想看的不是你用双重递归暴力数完，而是能不能想到用树上前缀和把复杂度降到O(n)。机考场景下，如果数据规模给到几万节点，暴力解法大概率超时，所以这道题值得把前缀和思路彻底吃透。它考的不只是DFS，还考“递归进入子节点时状态怎么维护、返回父节点时状态怎么撤销”，这个能力在实际工程里处理嵌套遍历时也很有用。
1.2 1208属于“滑动窗口”模板题
1208的题面是“尽可能使字符串相等”，给两个长度相同的字符串s和t，再给一个预算maxCost。你可以选s中一段连续子串，把这段每个位置的字符都改成t对应位置的字符，每个位置的开销是它们ASCII码的差值的绝对值，问预算内最多能转换多长的连续子串。
这个题在LeetCode上是中等难度，但它本质上就是一个标准滑动窗口模板题，比437还要套路化。关键步骤是先把每个位置的代价算出来，得到一个非负整数数组，然后题目就变成了“最长连续子数组，使得子数组和不超过maxCost”。这种包装很常见，机考里大量题目都是把一个数组或字符串连续段的问题，套上一个生产背景，比如资源分配、任务调度、连续库存控制等，识别出滑动窗口模型就是拿分的关键。1208的训练价值就在这里：它帮你建立从复杂题面到经典模型的映射能力。
1.3 两题的底层逻辑：连续段累计与预算限制
把两题放在同一张表里看，思路会清晰很多。437求的是“树上满足路径和等于targetSum的路径数量”，核心是前缀和加哈希表统计出现次数；1208求的是“数组里满足子数组和不超过maxCost的最长长度”，核心是滑动窗口维护窗口内代价。一个是统计数量，一个是求最大长度；一个可以用前缀和快速计算任意段的和，一个用双指针在线维护当前段的和。
它们共享同一个数学基础：连续段的累计值可以通过前缀和的差值表达。437是preSum[B] - preSum[A] == targetSum，1208是preCost[right+1] - preCost[left] <= maxCost。前者用哈希表加速查找目标差值，后者用单调不减的性质让窗口左指针只会右移。理解了这层对称性，刷题就不是一道一道硬背，而是一个模型一个模型吃透。
2. 437路径总和III：从暴力DFS到前缀和回溯
2.1 先理解437的路径定义与边界条件
437里“路径”这个词容易让人想当然。它不要求从根出发，也不要求到叶子结束，只要求方向向下且连续。举个简单例子：根节点值是5，左孩子是2，右孩子是-3，targetSum是2。那么“左孩子单独一个节点”算一条路径，和是2；“根到右孩子”这条路径和也是2，算一条路径；“根节点自己”和等于5，不算；“根到左孩子”和等于7，不算。节点值可以是负数，这一点极其关键，后面所有剪枝陷阱都从这里来。
还要注意的是，路径不能拐弯。比如某个节点既有父节点又有左子树，我们不能统计“祖父到父再拐到当前节点的兄弟叶子”这种路径，因为方向必须保持从上到下同一个分支。所以暴力解法里，枚举完当前节点作为起点的所有路径后，只能继续在左右子树里找新的起点，而不能先把路径延伸到父节点再折返。
2.2 解法一：双重递归，思路最直白
最容易写出来的版本是双重递归。外层递归遍历树上的每个节点，把它当作路径起点；内层递归从这个起点往下延伸，累加路径和，命中targetSum就计数。
class Solution { public int pathSum(TreeNode root, int targetSum) { if (root == null) return 0; return countFrom(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum); } private long countFrom(TreeNode node, long target) { if (node == null) return 0; long res = 0; if (node.val == target) res++; res += countFrom(node.left, target - node.val); res += countFrom(node.right, target - node.val); return res; } }注意这里为什么是“当前节点作为起点的路径数”加上“左右子树内部的路径数”。因为起点可以是任意节点，所以不能只算以根为起点的路径，还得递归到左子树、右子树里继续枚举起点。countFrom里用target - node.val去递归，相当于把“剩余需要凑的和”传给子节点，这是从根到叶子累加思路的变体，代码上非常干净。
这个解法的复杂度是O(n^2)，最坏情况是二叉树退化成一条链，每个节点都要向下遍历剩余的所有节点。如果机考数据规模是几千个节点，可能还能过；如果是几万个节点，大概率超时。它在实战里的价值是当备用方案：如果一时想不起前缀和解法，先写暴力保住部分测试点，再回头优化。
2.3 解法二：前缀和加哈希表，一次DFS搞定
要降到O(n)，核心观察是：从根到任意节点的路径上，前缀和是不断累加的。那么任意一条从祖先A到后代B的路径和，可以表示为preSum[B] - preSum[A]。如果这个值等于targetSum，就说明路径A->B满足条件。变换一下公式就是preSum[A] = preSum[B] - targetSum。
所以在DFS遍历时，维护一个哈希表map，记录“从根到当前节点路径上，每个前缀和值出现过多少次”。到达任意节点B时，查询map中preSum[B] - targetSum出现的次数，就得到了以B为终点、起点在其祖先链上的所有合法路径数量。这里前缀和0也要预先put进map，次数为1，表示空路径前缀，否则从根节点开始的路径会被漏算。
这个思路放到树上，实现时必须处理一个问题：树的DFS是一路延伸到叶子再返回的，当你从左子树返回父节点，准备进入右子树时，map里还留着左子树的前缀和信息。如果不清理，右子树会把左子树里的前缀和误认为祖先链上的前缀和，统计出大量不存在的路径。解决办法就是回溯时恢复现场，把当前节点对应的前缀和计数减一，减到0就删除key。
2.4 完整代码与四个易错点
import java.util.HashMap; import java.util.Map; class Solution { private int ans = 0; public int pathSum(TreeNode root, int targetSum) { Map<Long, Integer> map = new HashMap<>(); map.put(0L, 1); dfs(root, 0L, targetSum, map); return ans; } private void dfs(TreeNode node, long preSum, int targetSum, Map<Long, Integer> map) { if (node == null) return; preSum += node.val; ans += map.getOrDefault(preSum - targetSum, 0); map.put(preSum, map.getOrDefault(preSum, 0) + 1); dfs(node.left, preSum, targetSum, map); dfs(node.right, preSum, targetSum, map); map.put(preSum, map.get(preSum) - 1); if (map.get(preSum) == 0) { map.remove(preSum); } } }第一个易错点是map必须先put(0L, 1)，没有它，targetSum恰好等于根到某节点整段路径和时会漏计。第二个是前缀和用long，题目节点值范围是正负一千万，极端情况下累加会超过int范围，这个我在自测时用极端数据跑出过负数结果。第三个是回溯恢复现场的顺序，必须先恢复再返回，不能把恢复放到左右子树递归之前。第四个是不要用节点值的正负做剪枝，哪怕当前累计和已经超过targetSum也要继续往下走，因为后面可能有负数把总和拉回来。
2.5 与560“和为K的子数组”的联系
做437之前，建议先把560做了。560是数组版：给一个数组，统计有多少个连续子数组的和等于K。数组版的解法也是前缀和加哈希表，但完全不需要回溯，因为数组从左往右扫一遍，每个位置只处理一次，不存在兄弟子树污染的问题。
437等于在560上套了一层树的递归外壳。树的DFS天然是“走下去再退回来”的，所以哈希表的增删必须跟随递归的进入和返回。你甚至可以这样理解：560是“线性路径上的前缀和”，437是“树上的前缀和加上回溯撤销”。把这两道题对照着刷，前缀和范式才算真正内化。机考再出“树上求和为K的路径数量”这类变体，你不需要猜解法，一眼就能定位到同一个套路。
3. 1208尽可能使字符串相等：变字符串为代价数组
3.1 先把题目翻译成数组题
1208题面里的字符串很长，但真正有用的信息只有一句话：每个位置的替换代价是两个字符ASCII码差值的绝对值。把s和t逐位相减取绝对值，得到一个非负整数数组cost，原来的子串连续变换问题就变成了“在cost数组中找一个最长的连续子数组，使子数组和不超过maxCost”。
这一步翻译是整个题的核心。我见过不少人拿到1208直接去考虑动态规划或者递归，其实是把简单问题复杂化了。字符串只是一个包装，去掉包装就是最经典的滑动窗口。非负这个性质也很重要，因为窗口内代价只会随右指针扩展而增加，不会自己降下来，这保证了左指针可以安全地持续右移，不用回头。
3.2 滑动窗口标准解法
滑动窗口的框架是固定的：右指针向右扩展，把新位置的代价累加到窗口和里；如果窗口和超过预算，就让左指针向右收缩，减掉离开位置的代价，直到窗口重新合法；最后用当前窗口长度更新答案。
class Solution { public int equalSubstring(String s, String t, int maxCost) { int left = 0; int cost = 0; int ans = 0; for (int right = 0; right < s.length(); right++) { cost += Math.abs(s.charAt(right) - t.charAt(right)); while (cost > maxCost) { cost -= Math.abs(s.charAt(left) - t.charAt(left)); left++; } ans = Math.max(ans, right - left + 1); } return ans; } }这里有个顺序细节必须强调：一定是先while收缩窗口，再更新ans。如果把更新写在while前面，你会在窗口还非法的时候用它的长度刷新答案，导致结果偏大。这个错误在样例数据小的时候不容易暴露，一旦maxCost很小，答案就会明显超预期。
还有一个边界情况处理：如果某个位置的单独代价已经超过maxCost，窗口会在那一位被迫收缩成空，right继续往前走，left可能变成right + 1，此时right - left + 1是0或者负数，Math.max不会错误增大ans，所以代码里不需要额外写if判断。我第一次写的时候在这里犹豫很久，后来验证了left可以超过right，逻辑依然是安全的。
3.3 双指针为什么是O(n)：left可以不停右移的秘密
初学者最容易问的问题是：right只往前走一步，left也只会往前走，为什么这样不会漏掉更长的合法窗口？
关键在于窗口维护的是一个“右端点固定时的最右侧合法左端点”。假设在某个right下，最优窗口是[i, right]，那么当right移动到right+1时，新的最优窗口左端点不可能比i更靠左，所以left只需要保持不动或者继续右移。因为所有代价都是非负的，窗口总和不会因为right的右移而下降，一旦窗口非法，把left右移是最合理的修复方式；而left已经右移越过的地方，在后续更大的right下更不可能重新成为合法窗口的左边界。两个指针各自最多移动n次，总复杂度O(n)。
对比暴力的O(n^2)，滑动窗口的优化本质是去掉大量被剪掉的枚举区间。机考里时间限制通常卡得紧，这种线性解法是必须第一时间想到的，而不是最后优化时才用。
3.4 另一种解法：二分长度加前缀和
如果面试官追问“还有没有其他解法”，可以用二分答案配合前缀和。因为代价数组非负，所以“是否存在长度为len且子数组和不超过maxCost的区间”这个判断，对len是单调的：len越大越难满足。可以二分长度，对每个len用前缀和判断。
class Solution { public int equalSubstring(String s, String t, int maxCost) { int n = s.length(); int[] pre = new int[n + 1]; for (int i = 0; i < n; i++) { pre[i + 1] = pre[i] + Math.abs(s.charAt(i) - t.charAt(i)); } int lo = 0, hi = n; while (lo < hi) { int mid = (lo + hi + 1) >>> 1; if (check(pre, mid, maxCost)) { lo = mid; } else { hi = mid - 1; } } return lo; } private boolean check(int[] pre, int len, int maxCost) { for (int start = 0; start + len < pre.length; start++) { if (pre[start + len] - pre[start] <= maxCost) { return true; } } return false; } }复杂度O(n log n)，比滑动窗口慢，但在机考里也能通过。它最大的意义不是替代滑窗，而是在面试交流时体现你理解多个解法的取舍。注意，这个二分依赖数组非负，如果题目改成代价可能为负，二分就失效了，因为单调性被破坏。1208里代价是绝对值，天然非负，所以能用。
3.5 与437的对称性：同一模型的两个方向
把437和1208放到一起看，会发现它们正好是连续段模型的两个方向。
437是“统计和为targetSum的段有多少”，解法是前缀和加哈希表统计次数；1208是“求和不超预算的段最长是多少”，解法是滑动窗口维护窗口和。一个需要精确匹配等于某个值，所以用哈希表加速查找；一个是求满足上下限的最大值，所以用双指针单调收缩。两者都用到了每个位置的累计值，差别在于437把累计值差精确相等作为条件，1208把累计值差不超上限作为条件。
这个对偶关系在机考刷题里很常见。刷完这两道，你会形成一种直觉：见到“连续段”加“等于K”，优先想前缀和加哈希表；见到“连续段”加“不超过预算”，优先想滑动窗口。这种模式识别能力，比背一百道题的题解都管用。
4. 机考实战：时间线与代码细节复盘
4.1 我在第14、15天的刷题过程
第14天刷到的是1208。我一开始被题面绕了一下，想用动态规划硬上，后来把cost数组一列出来，顿时看清是滑窗模板，大概4分钟写完主逻辑，5分钟在本地跑测试用例。真正卡住我的不是滑动窗口本身，而是“连续子串”对应“数组连续段”这个映射，一旦映射没建立起来，后面全是瞎忙。这次经历让我养成了一个习惯：遇到字符串连续变化问题，第一反应不是去匹配字符，而是先把逐位代价数组算出来。
第15天刷到的是437。因为前一天刚刷过560，我自然想到了前缀和，但一上来就漏了map.put(0L, 1)，样例输出总是少1。排查过程很痛苦，最后是在纸上手动模拟了从根开始的一条路径，才发现根路径被漏了。另一处坑是恢复现场：我一开始只把计数减一，没有删除归零的key。结果不影响数值正确性，但调试时打印map，里面全是值为0的残留条目，干扰判断，后来改成减到0就remove，日志清爽多了。
这两天的经历让我确信一个复习策略：刷题不能按题号顺序机械推进，应该按模型归类。1208和437在题号上隔得很远，但本质上都在处理“连续段累计值”的问题。把它们放一起复盘，远比今天刷链表、明天刷树、后天刷字符串这种散点式刷法高效。
4.2 易错点清单
| 题目 | 易错点 | 后果 | 解决办法 |
|---|---|---|---|
| 437 | map缺少初始条目(0,1) | 从根开始的路径被漏算 | 直接先put(0,1)再dfs |
| 437 | 回溯时没恢复现场 | 统计到兄弟子树结果偏大 | 递归返回后计数减一，减到0删key |
| 437 | 累加和用int | 极端数据溢出 | 前缀和变量用long |
| 437 | 用累计和大小做剪枝 | 负值节点导致漏解 | 只做查找，不做大小比较剪枝 |
| 1208 | 忘记Math.abs | 负代价打乱窗口判断 | 每个位置都取绝对值 |
| 1208 | 先更新答案再收缩窗口 | 非法窗口刷新答案 | 收缩完毕再Math.max |
| 1208 | s和t长度不一致或为空 | 越界或死循环 | 开头判空，n为0直接返回0 |
这个表是我后来整理了所有刷题记录里总结出来的。每次做错题，我不光看正确解法，还会把错误原因写进对应表格里，考前翻一遍比临时刷十道新题有用。
4.3 从核心代码模式切到ACM模式的改造
很多机考平台给的是核心代码模式，函数签名固定，你只需要填实现。但也有不少平台是ACM模式，输入输出全要自己写。1208如果遇到ACM模式，可以这样组织：
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.nextLine(); String t = sc.nextLine(); int maxCost = Integer.parseInt(sc.nextLine().trim()); int left = 0; int cost = 0; int ans = 0; for (int right = 0; right < s.length(); right++) { cost += Math.abs(s.charAt(right) - t.charAt(right)); while (cost > maxCost) { cost -= Math.abs(s.charAt(left) - t.charAt(left)); left++; } ans = Math.max(ans, right - left + 1); } System.out.println(ans); sc.close(); } }注意nextInt和nextLine混用时的换行吞字符问题，我习惯全部按行读，再用Integer.parseInt处理数字，省得遇到输入格式的坑。437的ACM模式更麻烦，因为需要自行根据输入建树，不同题面给的输入约定不一样，有可能是层序遍历序列，也有可能是父子关系对。机考时如果遇到需要建树的输入，先看清楚格式，再用队列或递归把树建出来，算法本身在核心代码模式里已经写好了，不要因为输入解析丢分。
4.4 自测用例与反例
1208我建议至少自测三组。第一组，maxCost为0时，答案应该等于s和t的最长相等前缀长度，比如s="abcd"，t="abce"，答案3。第二组，maxCost非常大时，答案应该等于字符串长度，比如s="ab", t="cd", maxCost=100，答案2。第三组，某一单独位置代价超过maxCost时，窗口要能跳过该位置，比如s="ab", t="cd", maxCost=0，答案0。
437的自测建议画一棵包含负数的三层树。比如根节点5，左孩子2，右孩子-3，targetSum设为2。手算预期结果是：左孩子单独算一条；“根到左孩子”和为7不算；“根到右孩子”和为2算一条；右孩子单独为-3不算。然后在递归入口和出口打印map，逐行核对前缀和的增加和删除，确认负数节点没有破坏前缀和的统计逻辑。这种手算加打印的调试过程，比直接AC一道题更能发现自己的理解漏洞。
5. 常见问题排查与刷题扩展建议
5.1 437结果偏大的典型根因
437返回结果比正确答案大，首要怀疑对象是回溯时map没恢复干净。典型场景是父节点下有两个子树，DFS先走完左子树，map里留下了左子树产生的前缀和；如果回到父节点时不把这些信息撤销，那么进入右子树时，右子树会把左子树的前缀和误认为祖先链上的前缀和，凭空多统计出大量路径。排查方法是在dfs函数入口和出口各打印一次map内容，对比增删记录，一眼就能看出现场是否恢复。
我还遇到过一种隐蔽情况：map里value减到0但没有remove。它不会导致答案错误，因为查询时计数为0不会贡献任何路径，但如果你在调试时打印map，里面全是value为0的历史key，会让人误以为还有很多路径在用这些前缀和，严重干扰判断。所以代码整洁性在实战中不是小事，尤其机考环境没有好用的IDE调试工具，日志清爽能救你一次。
5.2 437结果偏小的典型根因
结果偏小最常见的原因是map没初始化(0,1)。这个bug非常隐蔽，因为大部分测试用例能正常通过，只有遇到“从根到某个节点的整段路径和恰好等于targetSum”时才会暴露。比如targetSum等于根节点值，走到根节点时preSum等于根值，查preSum - targetSum = 0，map里没有0就直接跳过这条路径，答案少了1。
另一个偏小原因是用了int类型保存前缀和。节点值累加超过int范围后会变成负数，preSum - targetSum自然算错，导致统计结果不稳定。自测时如果发现同一棵树的答案在不同参数下出现莫名其妙的跳变，优先检查是不是溢出。
5.3 1208答案总是1或0
答案一直是1，要分两种情况。一种是你忘了Math.abs，导致某些位置的代价是负数，正负抵消后窗口误以为开销很小，这种现象通常会让答案偏大而不是固定为1，所以不是首选怀疑对象。另一种是代价数组里每一项都超过maxCost，窗口每次只容纳一个元素就被收缩，答案自然固定在1。这时检查maxCost是否过小，或者字符串里是否全是差异很大的字符。
答案一直是0，多半是输入解析问题。ACM模式下s和t没读对，或者读进来的字符串为空，长度n是0，循环根本没进去。另外如果s和t长度不一致，滑窗代码在循环里会越界，好的做法是先判断长度相等再做字符访问。
5.4 1208答案更新的顺序：先收缩还是先更新
这个坑很小，但真要踩了很头疼。正确顺序是while收缩窗口之后，再用right - left + 1更新答案。如果把Math.max写在while前面，窗口可能还是非法的，长度偏大。样例数据如果宽松，碰巧能过，但隐藏用例里只要maxCost比较小，答案立刻错乱。
我建议把“先收缩，后更新”当成滑动窗口的固定动作顺序来记忆，和“先判断，再操作”是同一类编程习惯。这个习惯还能延伸到其他双指针题目，比如求最短窗口、求包含所有字符的窗口，顺序逻辑都一样。
5.5 配套练习与扩展方向
想把这个模型练扎实，可以按方向补题。数组前缀和方向：560和为K的子数组、523连续的子数组和、974和可被K整除的子数组，这三道把前缀和加哈希表的变体都覆盖了。滑动窗口方向：209长度最小的子数组、1004最大连续1的个数III、904水果成篮，这三道把窗口收缩条件练熟。树路径方向：124二叉树中的最大路径和，它不要求路径必须向下，递归返回值要同时维护“包含当前节点的单边路径”和“全局最大路径”，和437的递归结构同源但不同难度。
如果你机考时间紧，建议不要贪多，每天只抓一个模型，把“数组版、树版、字符串版”各做一道，比一天刷十道不同题型效果好得多。我第14、15天就是按这个方法做的，437和1208的复盘收益远超预期。
提示：机考刷题最容易掉进的陷阱是按题号顺序刷完就扔。每做完一道题，花五分钟想想它属于哪个模型，和哪几道老题共享核心思路，这五分钟比你多刷三道新题更有价值。
这两道题是我第14、15天的刷题复盘，最大的感受是：很多题看起来是新的，拆开全是旧模型的变形。437是数组前缀和问题在树上套了一层递归回溯，1208是数组连续段和问题在外面包了一层字符串壳。刷到后面，比的不是谁见过的题多，而是谁能在五分钟内把一个新题映射到熟悉的模型上。我自己的做法是给每个模型建一张卡片，卡片上贴一道最典型的题、一份模板代码、一个必踩的坑，机考前一天只翻卡片，不刷新题。如果你也是机考冲刺阶段，不妨试一试这种复盘方式，把每天刷的两道题往模型里归类，长期下来绝对比漫无目的地按题号刷更稳。
