Day6编程练习复盘：滑动窗口、快慢指针与层序遍历实战

第六天。说实话，能连续刷题六天，比我预想的要难不少。第一天打开题库，连题目描述里的术语都要反复查；到了今天，至少看到中等难度的数组题、链表题、二叉树题，心里已经能快速判断“这题大概考什么套路”。这个编程题练习系列走到Day6，我想认真记录一下这天的选题思路、做题过程、踩过的坑，以及坚持六天后真实的感受变化。如果你也正处在刷题起步阶段，或者刚好卡在“每天都在练但感觉没进步”的瓶颈里，这篇Day6练习复盘应该能给你一些参考。

今天的三道题，我没有刻意去啃难题，而是选了三个高频且经典的方向：滑动窗口解决最短覆盖子串、快慢指针寻找链表环入口、二叉树的层序遍历变形。选这个组合有两个原因：一个是这三个套路在面试和笔试中出现的频率确实高；另一个是，Day6这个阶段最该做的不是挑战极限题，而是把基础套路真正内化，让它们能组合起来解决新问题。下面我会把每道题的完整思路、代码实现、常见错误都拆开讲，也会分享一些题外的方法论。

1. 第六天的选题思路：为什么练“组合基础”而不是硬啃难题

到第六天，很多人容易陷入两个极端：要么觉得基础题刷腻了，想去碰难题；要么还是只敢刷最小白题，不愿意提升难度。我两边都不想选，所以特意把今天定位成“基础能力组合应用日”。

1.1 前五天的进度复盘：给自己定位

我给自己定的计划是每天一到两小时，不用贪多，但必须保证每道题都吃透。Day1到Day2集中刷数组和字符串的基础题，Day3专门练哈希表的应用，Day4把链表的基本操作（反转、合并、删除节点）过了一遍，Day5刚开始接触二叉树，只做了前中后序遍历和简单的递归。这样走到Day6，基础数据结构基本都见过一遍，但说实话，当时的状态是“单个套路好像都懂，一旦题目把两个知识点的考察混在一起，就会卡住”。

这种“单个会、组合卡”的状态，是刷题起步阶段最典型的瓶颈。如果这时候急着去挑战最难的动态规划或图论，很容易被打击到心态，而且就算AC了也大概率是靠记忆题解，不是真理解。所以我给Day6定的目标很明确：通过三道“基础结构组合应用”的题目，把前面学到的东西真正串起来，让自己开始习惯从“这个知识点我背过”过渡到“这个场景下我应该用哪个知识点的组合”。

1.2 今天的做题标准：套路明确、边界丰富、能迁移

选今天这三道题之前，我给自己列了三个筛选条件：首先，它得是高频面试题，刷一道能解决一类问题；其次，它必须有明确的套路可循，方便我整理成模板；最后，它必须包含足够多的边界情况，能锻炼我的调试能力。三个条件缺一不可，因为Day6的练习绝对不是“随便找三题做做”。

拿最终选出的三道题来说：最短覆盖子串属于“滑动窗口+哈希计数”的组合，链表环入口属于“快慢指针+数学推导”的组合，自底向上层序遍历属于“队列BFS+结果处理”的组合。它们没有一个需要特别冷门的算法知识，但对基础数据结构的要求都比较扎实，正好匹配Day6的位置——既不吃力，又能让你感觉到“题目开始有点综合了”。我也不建议刚刷题的人一上来就给自己定“每天五道题”这种目标，质量比数量重要太多，一天把三道题完全吃透，比一天过十道题却只留个印象要有用得多。刷题是一个需要长期坚持的事，节奏稳定比短期冲刺更可持续。

2. 核心题目拆解：三道题背后的算法思维

下面按顺序讲今天的三道题，每道题我都会给出可运行的Python代码和完整的复杂度分析。语言方面我选了Python，因为它在刷题场景下最省事，但思路完全可以用C++或Java复现。三道题分别覆盖数组、链表、二叉树三个基础数据结构，正好串起前五天的练习内容。每道题我都按“题目描述→核心思路→代码→坑点复盘”的顺序展开，方便你照着练习，也方便以后回头翻阅。

2.1 数组与哈希：最短覆盖子串的滑动窗口模板

题目描述是这样：给定一个字符串s和一个字符串t，请在s中找出包含t所有字符的最短子串，返回最短长度；如果不存在，返回0。t中的字符可能出现重复，比如s = "ADOBECODEBANC"，t = "ABC"时，最短子串是"BANC"，长度4。

这题实际上是“滑动窗口”和“哈希计数”两个知识点的叠加。暴力做法是枚举所有子串，再逐个检查是否包含t的所有字符，时间复杂度是O(n^3)：枚举起点终点要O(n^2)，检查每个子串又要O(n)。n稍微大一点基本就跑不过了，所以必须用滑窗把枚举+检查这个过程压成一遍扫描。

from collections import Counter def shortest_cover(s: str, t: str) -> int: if not s or not t: return 0 need = Counter(t) missing = len(t) left = 0 ans_len = float('inf') for right, ch in enumerate(s): if need[ch] > 0: missing -= 1 need[ch] -= 1 while missing == 0: ans_len = min(ans_len, right - left + 1) need[s[left]] += 1 if need[s[left]] > 0: missing += 1 left += 1 return ans_len if ans_len != float('inf') else 0

第一个关键点是missing变量的设计。很多新手喜欢把“检查窗口是否覆盖t”写成单独的函数，每次窗口变化都重新统计一遍，这样窗口每移动一次就是O(t)的开销。我的做法是维护一个“还缺多少个字符”的计数器：只有当need[ch]大于0时，说明这个字符是t里仍然缺的，此时右指针扫过它，缺失数才减1。如果字符根本不在t里，need[ch]会变成负数，missing不受影响，但哈希表里必须记录这个变化，因为左指针收缩时要精确还原频次。

第二个关键点是收缩条件。窗口满足条件后，不能光更新答案，还要尝试把左指针往右移，看能不能在保证覆盖的情况下把子串缩到更短。收缩时，need[s[left]]加回1，如果这个字符重新变成“必需但缺失”的状态，missing加1，循环退出。这一套“右扩左缩”的逻辑，就是滑动窗口框架的核心。

注意：滑动窗口模板里，need这个计数器既可能变成负数（表示窗口里有多余字符），也可能重新变回正数（表示又开始缺这个字符了）。理解这一点，才能理解收缩循环的退出条件。

复杂度非常理想：每个字符最多被右指针扫一次、被左指针扫一次，整体O(n)；need字典的空间开销是O(|t|)。这类题思路通了以后，代码就那十行，真正难的是理解missing和need之间的配合关系，而不是把代码背下来。

2.2 链表与数学：找出环入口的快慢指针

题目描述：给定一个单链表，如果链表中有环，返回环的入口节点；如果没有环，返回None。这题经常被拆成“判断是否有环”和“找环入口”两个小问，今天直接合并成一道完整题目来练。

先用快慢指针判断有没有环：slow每次走一步，fast每次走两步。如果fast先到链表尾部，说明无环；如果slow和fast相遇，说明有环。第一次相遇时的位置不一定是环入口，所以要再走一次数学推导：设链表头到环入口的距离为a，入口到相遇点的距离为b，相遇点到入口的剩余距离为c，环长度L = b + c。相遇时slow走了a + b，fast走了a + b + kL，其中k是fast在环里多绕的圈数。因为fast走的路程是slow的两倍，就有2(a + b) = a + b + kL，化简得a + b = k*L，进一步推出a = (k-1)*L + c。这个式子说的是：从头节点出发的指针，和从相遇点出发的指针，都一步步往前走，它们一定会在环入口处碰上。

def detect_cycle_entry(head): if not head or not head.next: return None slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: break if not fast or not fast.next: return None ptr = head while ptr != slow: ptr = ptr.next slow = slow.next return ptr

这段代码有两个我必须单独拿出来说的坑。第一个是while循环的终止条件。fast = fast.next.next要求fast和fast.next都不能为None，所以循环条件必须写while fast and fast.next，而且两个条件的顺序不能变。如果你先判断fast.next，一旦fast本身是None，空指针异常就来了。这种顺序细节看起来小，但几乎每个新手都会在这里卡一次。

第二个坑是无环情况的收尾。循环正常结束后，slow可能已经走到了链表的某个中点，它跟“环入口”半毛钱关系都没有。判断无环要看fast是否走到了链表尾部——也就是fast为None或fast.next为None。必须加上if not fast or not fast.next这个保护判断，然后再进入找入口的二次循环，否则你把slow当作入口返回，遇到无环用例时答案就是错的。

提示：快慢指针相遇后不能直接返回相遇点，必须先从头节点再走一趟，第二次相遇的位置才是环入口。这个结论可以直接用距离公式记住：a = (k-1)*L + c。

复杂度方面，时间O(n)，空间O(1)。快慢指针是链表题里出镜率最高的技巧，除了找环，还常用于找链表中点、找倒数第k个节点，把这一道题吃透，等于同时带出了好几个知识点。

2.3 二叉树与队列：自底向上层序遍历的实现

题目描述：给定一棵二叉树，自底向上逐层返回所有节点值。比如根节点是3，左孩子9，右孩子20，20的左孩子15，右孩子7，最后要返回的结果就是[[15,7],[9,20],[3]]——底层在前，根层在后。

这题的核心是层序遍历，也就是广度优先搜索BFS。层序遍历有一个非常固定的模板：借助队列，根节点先入队；每次从队列左侧弹出节点，记录值；再把它的左孩子、右孩子依次入队；循环到队列为空。因为要区分“每一层”，还得加一个技巧：每轮循环开始时，先把当前队列长度n存下来，然后只弹出n个节点，这n个节点恰好就是当前层的全部节点。用for循环控制弹出的次数，而不是把弹出和入队混在一起，这样level列表才能保存每一层的值。

from collections import deque def level_order_bottom(root): result = [] if not root: return result q = deque([root]) while q: level = [] for _ in range(len(q)): node = q.popleft() level.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) result.append(level) return result[::-1]

这里为什么用deque而不是Python的list加pop(0)？因为list.pop(0)的时间复杂度是O(n)，每次弹出都涉及后面所有元素整体前移，层内节点比较多时累积性能很差。deque是双向队列，popleft()均摊O(1)，是BFS场景的标准选择。

拿到从上到下的层级列表后，直接[::-1]反转就是自底向上的结果，整体复杂度O(n)，额外空间O(n)。如果面试中碰到“能不能不反转”的追问，一种想法是把每层结果insert(0, level)，但Python的insert(0, ...)也是O(n)操作，多次插入反而更慢，所以直接反转反而是最高效的。能在代码里讲清楚这个取舍，会比单纯背模板显得更扎实。

今天这三道题，正好把基础的数据结构能力都覆盖到了。做完之后，我还顺手整理了一个“套路速查”：遇到子串/子数组问题先想滑动窗口，遇到链表环/中点问题先想快慢指针，遇到树的按层问题先想队列BFS。这种归纳本身就是Day6练习的一部分。

3. 实操记录：从读题到AC的三个阶段

这一节记录的是我实际做题时的完整流程，而不是理想化的标准流程。很多人刷题时会跳过一些看起来“不必要”的步骤，比如画样例、先写暴力解、整理错误表格，但这些步骤恰恰是最省时间的。把它们单独列出来说，是因为它们比多刷十道题更能决定你能不能稳定进步。

3.1 先画样例再写代码：别急着敲键盘

每次读完题，我给自己一个硬性要求：先在草稿纸上写一个不超过10个节点的样例，然后用手工的方式把样例完整跑一遍。这个习惯从Day1就开始练，到今天已经快变成肌肉记忆了。

拿最短覆盖子串举例。s = "ADOBECODEBANC"，t = "ABC"。手工推的时候，我会把左指针固定在最左端，右指针从0开始逐步右移，同时在心里默记“当前窗口里A、B、C各出现了几个，还缺几个”。右指针走到索引5时，窗口变成“ADOBEC”，A、B、C齐了，缺失数归零，记录当前答案长度6；接下来左指针右移到索引3，窗口变成“OBEC”，C还在但A没了，缺失数变回1，收缩停止。这样手工推完一遍，代码里每个分支应该怎么写，基本就清楚了。

这个过程看着慢，其实一道题只多花两三分钟，却可以省下后面写代码和调试的大量时间。因为手工推演会让你自然关注边界：窗口什么时候满足条件、收缩什么时候停止、答案在哪里更新。很多朋友看到题就立刻打开编辑器，一边写一边改，改到最后边界还是漏了，回头重新推演，反而更浪费时间。

3.2 从暴力解法到优化：先保证会，再追求快

我还保持着一个习惯：如果一道题五分钟内想不出最优解，就先把暴力解写出来，保证正确性后再优化。今天的三道题，除了层序遍历本身就比较模板化，另外两题我都在脑子里先过了一遍暴力方案。

最短路覆盖子串的暴力方案就是枚举所有子串，对每个子串用Counter统计字符频次，再和t做一个覆盖比较。代码写起来很简单，但复杂度是O(n^3)，跑小样例没问题，一上大的测试用例就超时。这时候回头分析“慢在哪”：因为窗口每次扩展和收缩都在重复统计整个子串的频次。优化的切入点就出来了——用哈希表动态维护窗口内频次，把“重复统计”改成“增量更新”。

这种“暴力 → 分析瓶颈 → 针对性优化”的路径，其实就是大部分标准解题思路的来源。Day6这一天给我最大的体会是，优化不是凭空想出来的，而是先拥有一个能跑的版本，再问自己“哪一步在做无用功”，答案往往就是优化的方向。

3.3 调试实录：今天真实踩到的三个坑

今天的三道题，我一道都没能做到一遍AC，记录几个真实踩坑点。

第一个坑在最短覆盖子串里。我把if need[ch] > 0: missing -= 1写成了if ch in t: missing -= 1。乍一看好像差不多，但t里有重复字符时就出事了。比如t = "AAB"，窗口里只出现了一个A，用in t判断就会错误地把missing减成0，窗口提前“假满足”，答案当然不对。正确逻辑应该是：need这个Counter里记录的是“还缺多少”，只有need[ch] > 0，说明这个字符是当前真正缺的，才能减少缺失数。

第二个坑在找环入口。快慢指针相遇后，我第一反应是“把slow当入口返回”。这个想法是错的，因为相遇点在环上，但不一定是入口。必须先让一个指针从链表头出发，和slow同步向前，两者再相遇时的位置才是环入口。如果你只练过“判断是否有环”的代码，很容易在这里翻车：判断有环是对的，但返回的节点是错的。

第三个坑在层序遍历的for循环里。我写的是for _ in range(len(q))，但循环体里又对q执行append操作。range(len(q))的len(q)只在进入循环时求值一次，但Python新手容易混淆动态长度的求值时机，结果循环次数失控。更稳妥的做法是先把当前层长度存到变量里，cur_len = len(q)，再for _ in range(cur_len)，这样即使循环体内改变队列长度，也不会影响本层处理次数。

把今天踩过的坑整理成一张速查表：

这张表我打算留到Day7再翻一遍，避免同样的坑犯第二次。

4. 刷题避坑与效率提升经验

第3节讲的都是今天实际遇到的坑，这一节再补充一些更通用的经验，也是我觉得坚持到Day6这个节点时，特别值得沉淀下来的内容。刷题过程中真正拖慢节奏的，往往不是某个算法不会，而是那些反复出现的边界错误、低效复盘方式和工具习惯。这些问题只要提前规避，每天能少浪费很多时间。

4.1 最常见的边界错误速查表

刷题这件事，边界情况才是真正的分水岭。思路对但边界漏了，照样过不了测试。我整理了这几天遇到频率最高的四类边界问题：

另外两个心得也很实用：第一，提交平台报错时，不要只看“WA”或者“TLE”，要复制出错用例到本地跑一遍，看它到底是在哪个断言失败。第二，遇到TLE先别急着整体重构，先用数据规模估算一下复杂度是不是真的有问题，有时候只是某一行代码多了一层不必要的O(n)循环。

4.2 高效复盘的三个提问

复盘这件事，比刷题本身更重要。我给自己定的规则是：每AC一道题，回答三个问题，做不到就说明这道题还没消化透。

第一个问题：这道题有没有更优的解法？今天的最短覆盖子串，滑动窗口已经是标准最优解，但我会再想想“如果t中字符很少是不是可以用其他数据结构”。第二个问题：我的解法在边界情况下都能通过吗？我会专门构造空输入、只有一个元素、全部元素相同这几个特例去跑。第三个问题：这个套路还能用在哪些题上？以快慢指针为例，AC了环入口之后，我会立刻联想到“找链表倒数第k个节点”、“找链表中点”、“判断回文链表”，它们本质都是同一套思想。这样复盘一道题，相当于复习三到五道同类题。

我还会把复盘写进本地笔记，不追求文采，关键是记录思考过程。Day6结束后我翻前几天的笔记，发现Day1写的滑动窗口模板旁边还有一行注释：“这里为什么收缩？”，当时没搞懂的问题，今天已经能讲清楚了。这种前后对比就是坚持记录最直接的正反馈。

4.3 工具与习惯：别让环境拖慢练习节奏

练习环境不用复杂，但一定要顺手。我目前用的方案是“本地编辑器 + 简单测试脚本”，每道题写完先跑一组本地用例再提交。这样能省下大量反复提交的时间，也方便随时调试。

测试用例一般固定四类：空输入、最小规模、常规规模、极端规模。比如链表题，我会准备空链表、只有一个节点、两个节点成环、长链表无环等用例。虽然看起来啰嗦，但每次提交前能跑一遍，心理会稳很多。

还有一个习惯是控制思考时间：读题两分钟，思考五分钟，不会就看题解。我见过一些朋友盯着一道题硬想一两个小时，最后既浪费时间又挫败感很强。五分钟没有思路就大方地看题解，看懂之后合上题解自己重新写一遍，这个“重写”的动作才是真正的学习闭环。

最后，建议把常用套路模板整理成个人速查笔记。滑动窗口、快慢指针、BFS层序、二叉树递归，每个模板都用自己的话重新写一遍，不要直接复制网上的。这个过程等于把“别人的理解”变成“自己的理解”。

5. Day6复盘：坚持六天后的真实变化

这一节不聊代码、不讲题目，就聊聊连续刷题六天给我带来的那些并不轰轰烈烈，但很实在的变化。这些变化不像AC一道题那么有成就感，却能让我在第七天早上醒来时愿意继续打开题单。它们也是我认为所有刚开始刷题的人都该提前知道的东西：坚持带来的回报，往往是延迟出现的。

5.1 从“背模板”到“理解模板”

刷题的前几天，我的学习方式很“机械”：看到“最长不重复子串”就套滑动窗口模板，看到“层序遍历”就套队列。到了Day6，题目开始把多个知识点组合起来，我发现自己没法靠背模板过关了，必须真正理解每个模板背后的逻辑链条。

比如滑动窗口模板里的missing和need为什么能同步变化，关键在“频次”两个字上。need不是简单的集合判断，它记录的是一个动态剩余的缺口。只有把整个字符频次的增减流程推演过一遍，才算真正理解这个模板怎么用。理解和不理解的差别，在Day6的三道题里体现得很明显：背模板的人遇到变体题会愣住，理解模板的人能把模板拆开重组，应用到新问题上。

坚持六天还有一个意外收获：遇到不会的题，焦虑感明显变低了。以前看到新题第一反应是“完了我不可能做出来”，现在会自然拆解：这题考的是数组还是链表还是树，大概率该用双指针、哈希还是队列递归。这套“扫描题目并归类”的能力，是在每天少量但高质量的训练里慢慢长出来的。

5.2 时间分配：每天1.5小时怎么安排

我这六天的练习时间基本稳定在1.5小时左右，具体分配如下：

如果某天状态不好，就减量不减质：哪怕只做一道题，也得把这道题吃透。我之前也尝试过一天刷五道题，结果到第三天就累得不想打开题库了。调整为“每天一到三道、质量优先”之后，反而能稳定坚持下来。刷题本质上是马拉松，不是百米冲刺，节奏感比单日强度重要得多。

5.3 下一步计划与给同样在坚持的人一个建议

Day7开始，我准备整理动态规划入门，先只做最简单的爬楼梯、打家劫舍这类线性DP，目标是建立“状态定义 + 状态转移方程”的思考方式。Day8到Day10继续巩固二叉树和双指针，同时每道题都坚持写复盘笔记，按“一句题目总结、核心思路、避免再犯的坑”三个部分来组织。

如果你也在做编程题练习，我特别建议把某一天专门当作复盘节点，不一定是第六天，但一定要有定时回看的习惯。刷题这个事最怕的，就是“刷了很多，却不知道自己到底学会了什么”。定期回头看看前几天的笔记，你会发现自己其实在实实在在往前走。拿我来说，Day1时连递归都要想半天，今天已经能流畅地把BFS模板写在纸上并解释每个步骤的原因——这种肉眼可见的变化，就是继续坚持下去的最大动力。

最后再分享一个小技巧：每次做完题，把当天用到的模板和踩坑记录存进一个固定的文件里，下次动手前先扫一眼，真的比临时翻论坛高效很多，也能明显感觉到自己正在一点点积累解题手感。这个方法不需要任何高级工具，一个笔记软件就够了，关键是要坚持记录。Day6的记录就到这里，我去准备Day7的题单了。各位也在坚持刷题的朋友，咱们明天见。