热题100刷题第十天：滑动窗口与双指针吃透无重复子串、回文和接雨水

1. 十天前我点开热题100，day10这天我准备写点不一样的

从第一天打开热题100到现在，已经过了整整十天。说实话，这个过程比我预想中更能暴露问题：前三天靠新鲜感，后面全靠复盘和刻意练习。今天是我在热题100的第10次打卡，主要任务是解决三道题——无重复字符的最长子串、最长回文子串、接雨水。它们看起来难度分布是中等、中等、困难，但共同点非常明显：全是字符串和数组问题，全都能用双指针或者滑动窗口的思路串起来。

如果你也在刷热题100，或者你正在为这几道题的边界条件头疼，这篇打卡总结可以给你一份偏实操的参考。我不打算把官方题解重新誊一遍，重点聊我在第10天真正动手写代码时遇到的选择、别扭和修正过程。毕竟打卡的意义不是“我今天又过了几道题”，而是“我有没有把每道题背后的通用思路带走”。

先说一个我觉得很重要的判断：热题100刷到中期，题目之间的关联性比难度更重要。前9天我还会按“简单题先刷完”的思路走，今天明显感觉不行。无重复字符的最长子串是典型的滑动窗口，最长回文子串可以用中心扩展，接雨水是双指针的集大成者。这三题放在同一天，不是为了凑数，而是因为它们背后都指向同一个核心问题：如何在一个线性结构上高效维护某个“区间状态”。

2. 第10天的选题逻辑与整体思路

2.1 为什么这一天集中刷“字符串+双指针”题

我在前几天的打卡里明显感觉到，双指针不是一个具体的算法，而是一种思维模式。不管是数组里找满足条件的区间，还是字符串里找某种对称结构，甚至是在柱状图里算水量，最后都能落到“用两个指针控制一个范围，并在移动过程中更新答案”这个模式上。

所以第10天我刻意没有去刷新类型，而是把之前几天的薄弱点集中暴露出来。无重复字符的最长子串考的是“窗口内的去重维护”，最长回文子串考的是“从中心向两边扩展”，接雨水考的则是“两侧高度差的实时计算”。这三道题如果分开刷，可能每道都能看懂题解，但很难形成手感。放一起刷，才能发现它们其实是在训练同一件事：指针往哪边动，动之前要记录什么状态，动之后要怎么更新答案。

我自己在刷题时有个习惯，每完成一道题都会在笔记上画一条“指针轨迹”。比如无重复字符的最长子串，窗口的左边界什么时候收缩，右边界什么时候扩张，每一步之后窗口内是什么状态。这道题画完轨迹，接雨水的双指针就更好理解了，因为脑子里已经建立了“指针移动的顺序决定信息更新顺序”这个直觉。

2.2 三道题在热题100里的定位与难度品味

热题100的题目顺序并不是严格按难度递增排列的，第10天正好撞上了几道比较有代表性的中等题和困难题。如果只看通过率，可能会觉得接雨水是最可怕的；但实际上，最长回文子串的代码虽然短，边界条件却特别容易错，尤其是奇偶长度回文的中心坐标计算。我前几次做这道题时，经常在返回值那里把左右索引搞混，一看就是半小时。

从面试角度说，这三道题都属于“高频中的高频”。无重复字符的最长子串几乎可以说是滑动窗口的入门必修课，最长回文子串则经常出现在“面试官想看你有没有真正理解回文结构”的场景里，接雨水更是很多人口中“背了答案也不一定能写对”的经典题。把它们放在第10天，是为了用中等题巩固思路，用困难题拔高一下。

我建议如果你也在做类似的打卡计划，第10天前后不要贪多。一天三道题完全够，甚至某一天只解决一道值得深挖的困难题也没问题。重点是当天要把解法吃透，能够不看题解独立写出代码，并且能讲清楚每一步为什么这么写。

3. 核心细节拆解：三道题背后的共同套路

3.1 无重复字符的最长子串：窗口怎么滑才不重不漏

这道题描述起来很简单：给定一个字符串，找出其中不含有重复字符的最长子串的长度。最容易想到的暴力做法是枚举所有子串，然后逐一检查是否有重复字符，时间复杂度O(n^2)到O(n^3)，字符串稍微长一点就跑不动了。

滑动窗口的做法是把“子串”抽象成一个窗口，窗口的左边界用left表示，右边界用right表示。right每次往右走一格，把新字符放进窗口；如果窗口内出现了重复字符，就移动left，直到窗口重新合法。关键是，这个过程中窗口的合法性是持续维护的，而不是每次从头检查整条子串。

我这里要强调一个细节：right作为遍历指针，其实是主循环里的那个变量；left的移动完全是被动触发的。很多人写这道题时容易把left的移动条件写成“出现重复字符就整体重置”，那就不对了。正确的逻辑是，当新字符已经存在于窗口集合中时，从左往右逐个移除左边字符，直到把那个重复的旧字符赶出窗口，然后才能把新字符放进去。这个“先收缩再扩张”的顺序不能颠倒。

3.2 最长回文子串：中心扩展为什么是面试稳妥答案

最长回文子串的解法有好几种，动态规划、马拉车算法、中心扩展法。马拉车算法能在O(n)时间内解决，但实现起来细节很多，面试时容易翻车。动态规划相对好理解，需要一张二维表格记录子串是否为回文，空间复杂度O(n^2)。中心扩展法是我第10天选择的主方案，因为它理解简单、代码量小，时间复杂度O(n^2)在大多数场景下足够用，而且面试时容易讲清楚。

中心扩展的核心思路是：回文串有一个“中心”，从中心向左右两边扩展，只要左右字符相等，就继续扩展；一旦不等，就停止。难点在于中心有两种情况：奇数长度回文的中心是一个字符，偶数长度回文的中心是两个字符之间的空隙。因此对于字符串里每个位置i，都要分别以i作为单字符中心去扩展，同时还要以i和i+1之间的空隙作为双字符中心去扩展。

有一个细节特别容易踩坑：两种中心扩展出来的回文长度可能一个是奇数一个是偶数，在计算左边界和右边界时不能套同一个公式。如果扩展得到的回文长度是curLen，那么起始位置start = i - (curLen - 1) // 2，结束位置end = i + curLen // 2。这个公式对奇偶两种长度都成立，关键是整除运算符在边界处的行为。我第10天专门用几种奇偶长度的样例验证过这个公式，才敢把这段代码写进笔记里。

3.3 接雨水：双指针解法是怎么一步步优化出来的

接雨水题目描述也不复杂：一组非负整数表示柱子高度，每根柱子宽度为1，问下雨后能接多少水。暴力思路是遍历每一根柱子，分别求出它左边最高柱子和右边最高柱子，用两者较小值减去当前柱子高度，就是当前位置的积水量。这个方法正确但慢，需要O(n^2)。

进阶做法是用前缀最大值和后缀最大值数组，两个数组都提前算好，再遍历一次求和，时间O(n)，空间O(n)。第10天我把这个方法也写了一遍，目的不是用它做题，而是为了理解双指针解法到底省去了什么。

双指针解法的核心是：让left从0开始，right从数组末尾开始，同时维护leftMax和rightMax。每次比较height[left]和height[right]，哪边小就处理哪边。为什么可以这样？因为对于left指针而言，只要height[left]小于height[right]，那么右侧的最高柱子起码是height[right]，左侧的最高柱子leftMax已知，所以当前位置能盛多少水只取决于leftMax和height[right]的较小值，而leftMax是已经确定的。反过来同理。这样就不需要提前知道右侧全局最大值，只需要在指针移动过程中不断更新左右各自遇到的最大值，空间降到了O(1)。

这里有一个我觉得很重要的领悟：双指针法能成立，靠的是“安全条件”。当height[left] < height[right]时，右边一定有足够高的柱子挡着，所以放心处理左边；反之亦然。这个安全条件的判断就是双指针移动方向的关键。很多人写反左右条件，本质上是没有想清楚这个逻辑。

4. 实操过程与代码落地

4.1 题目一实现：滑动窗口 + 哈希集合

先上代码。我用的是Python，字符集合用set来维护窗口内的字符。

def length_of_longest_substring(s: str) -> int: window = set() left = 0 ans = 0 for right, ch in enumerate(s): while ch in window: window.remove(s[left]) left += 1 window.add(ch) ans = max(ans, right - left + 1) return ans

这段代码的执行过程值得细看。以s = "abcabcbb"为例，right从0走到2时，窗口里依次存入a、b、c，ans变成3。right走到3时，ch是a，而a已经在窗口里，所以进入while循环，先从窗口移除s[left]也就是最左边的a，left变成1。此时窗口里有b、c，a已经不在窗口里了，循环结束，再把新的a加入窗口。窗口变成b、c、a，长度还是3。

注意while循环里每次只移除一个左边字符。这里有一个常见误区：有人会写成while ch in window: window.clear()，这会把整个窗口清空，结果漏掉了字符串中间的合法子串。正确做法是逐字移出，保持窗口内剩余字符的相对顺序。

4.2 题目二实现：中心扩展法的坐标计算

最长回文子串的中心扩展实现如下：

def longest_palindrome(s: str) -> str: if not s: return "" start = 0 end = 0 n = len(s) def expand(left: int, right: int) -> int: while left >= 0 and right < n and s[left] == s[right]: left -= 1 right += 1 return right - left - 1 for i in range(n): len1 = expand(i, i) len2 = expand(i, i + 1) cur_len = max(len1, len2) if cur_len > end - start + 1: start = i - (cur_len - 1) // 2 end = i + cur_len // 2 return s[start:end + 1]

expand(i, i)处理奇数长度回文，中心是单个字符；expand(i, i+1)处理偶数长度回文，中心是字符间的空隙。返回的right - left - 1是扩展后实际回文长度，这个公式在while结束时left和right已经越界到回文区域外，所以需要减1而不是加1。

坐标计算这里我第10天专门验证过。如果回文长度是奇数，比如"aba"，当i=1时cur_len=3，start=1-2//2=1-1=0，end=1+3//2=1+1=2，正确。如果回文长度是偶数，比如"abba"，当i=1时，以双字符中心扩展返回len2=4，cur_len=4，start=1-(4-1)//2=1-1=0，end=1+4//2=1+2=3，正确。这个公式的核心在于Python整数除法向下取整的特性，奇数长度下的(cur_len-1)//2和偶数长度下的cur_len//2自然对齐了。

4.3 题目三实现：左右双指针累计雨水

接雨水的双指针实现：

def trap(height) -> int: left = 0 right = len(height) - 1 left_max = 0 right_max = 0 ans = 0 while left < right: if height[left] < height[right]: if height[left] >= left_max: left_max = height[left] else: ans += left_max - height[left] left += 1 else: if height[right] >= right_max: right_max = height[right] else: ans += right_max - height[right] right -= 1 return ans

在处理左指针时，如果当前高度不小于左侧遇到的最大值，说明当前位置是个新出现的“高坡”，不能存水，只需要更新left_max；如果当前高度小于left_max，说明左右高坡之间存在洼地，可以存left_max减去当前高度的水。右指针同理。

我用height = [0,1,0,2,1,0,1,3,2,1,2,1]这个经典数据手工演算过：最终ans为6。整个过程中，left和right不断向最高的柱子收敛，最后停在最高柱附近。在left和right相遇时不需要处理最后这格，因为最高柱本身不会存水。

4.4 边界用例与复杂度速查表

每道题写完代码后，我都会跑一组边界用例。这里整理一下今天用到的用例，可以直接抄进自己的测试脚本里。

复杂度方面，我用如下总结：

• 无重复字符的最长子串：时间O(n)，空间O(min(n, 字符集大小))。每个字符最多被加入窗口一次，移除一次，所以虽然是双层循环结构，但总操作次数是O(n)。
• 最长回文子串：中心扩展时间复杂度O(n^2)，空间O(1)。每个中心最坏扩展到整个字符串长度。
• 接雨水：双指针时间O(n)，空间O(1)。相比前缀最大值数组的O(n)空间少了常数级内存，但代码理解难度略高。

5. 十天打卡踩坑实录：这些问题你可能也会遇到

5.1 滑动窗口的右指针到底该不该进while

我一开始写无重复字符的最长子串时，把循环结构写成了这样：外层while去移动left，内层for去移动right，结果left的更新逻辑一团乱。后来才想明白，right应该由主遍历驱动，left只在需要收缩窗口时进内层循环。也就是说，外层是for right，内层是while去重。这样窗口的状态才始终是连续的。

如果你发现自己的代码里出现了一个单独负责移动right的while循环，大概率是把问题复杂化了。还有一种错误是把while ch in window写成if ch in window。用if只能移除一个字符，但遇到"dvdf"这种字符串，right走到第三个d时，窗口内有d、v，如果用if移除最左边的d，窗口中还有v，再把新d放进去，窗口会变成v、d和v？不对，实际上是窗口内含v和d，但下标0的d和下标2的d重复了？那已经被移除了，窗口内是v和新d，无法解决下标1的v和下标3的v重复的问题。正确做法是while，持续移除直到窗口内没有与当前字符重复的字符。

5.2 回文子串的奇偶中心漏项

最长回文子串最经典的坑是只考虑了奇数长度回文。如果你只对每个位置i调用expand(i, i)，那"abba"这种偶数长度回文就完全检测不到。我第9天做这道题时就是这个问题，代码运行示例用的全是"aba"、"abcba"这种奇数回文，以为自己AC了，结果一提交，"cbbd"直接把我打回原形。所以第10天我在笔记里用红笔标注了：每个i必须扩展两轮，一轮单字符中心，一轮双字符中心。

另一个坑是expand函数里的循环边界。有些写法用while left >= 0 and right < len(s)判断边界，然后扩展。如果初始传入right = i+1，那么循环内可能遇到left和right相邻但字符相等的情况，但长度是偶数回文的最小单元是"aa"，也就是说left和right相邻时至少距离为1，字符串长度至少2。这个关系在坐标计算时要特别留意。

5.3 接雨水的双指针循环条件写反

接雨水代码里最危险的错误是把判断条件写成了if height[left] > height[right]。写反之后，逻辑看似对称，但left_max和right_max的更新时机完全错位，最终结果会偏大或偏小。我第10天故意做了一次实验，把条件改反，然后用手工用例跑了一轮，发现有些位置明明该处理左边，却跑到右边去更新right_max，根本说不通。

记住一个简单的判断标准：处理高度较小的一侧。因为较矮一侧的积水上限已经被“较高另一侧”保底了，这一侧可以安全结算。这个“安全”两个字是整个双指针接雨水解法的灵魂。

5.4 调试技巧：小数据手工推演比打印更高效

这三道题都可以在代码里加print来观察指针移动，但我的体会是，第10天真正提效的方式是拿一组小规模数据，在纸上手工画一遍完整过程。尤其是接雨水，每移动一次指针，都要记录left、right、left_max、right_max和ans五个变量的值。画完后，再对着代码逐行跑一遍，能立刻发现哪里有逻辑偏差。

比如无重复字符的最长子串，你可以拿"abcabcbb"做手工推演，把每一步窗口内容写出来；最长回文子串则拿"babad"和"cbbd"对照，看奇偶中心的索引计算；接雨水就按固定数组把双指针移动过程列成表格。这个过程看起来费时间，但做完之后，代码里的边界条件基本就焊死在脑子里了。

6. 坚持打卡十天的一些体会

我确实没想到自己能坚持到第10天。刚起步那几天，总有一种感觉：每天刷几道题，好像记不住多少。但到了今天，回头翻看前9天的笔记，发现那些当时觉得很难的题目，其实已经有了一些比较清晰的解题框架。

今天这三道题给我的最大收获是：很多经典题不是靠“见到即秒杀”，而是靠“见到后快速归类”。看到字符串子串问题，先想滑动窗口；看到回文问题，先想中心扩展；看到数组接水类问题，先想双指针。归类的准确度，来自于平时刷题时是否愿意多做一步——把每道题的思路和边界陷阱记录下来。第10天这个节点，我正好通过这三道题把双指针和滑动窗口的框架彻底整理了一遍。

如果你也在做热题100打卡，我的建议很简单：不要只追求数量，每天哪怕只做两道题，只要把思路写明白、边界跑清楚，都比囫囵吞枣刷五道更有用。第10天不意味着必须突破多少题，而是该沉淀一下前十天的套路了。打卡这事，贵在把每一道题都变成自己的工具，而不是仅仅当作一个完成列表上的勾。