★ FEATURED ARTICLE 1. 双指针与滑动窗口为什么值得死磕到底说实话刷题刷到一定阶段你会发现一个现象很多“看起来很难”的中等题本质上就是双指针或者滑动窗口。尤其是LeetCode上那些字符串、数组相关的题目十道里面有四五道都能用这套思路解。我之前也走过弯路一上来就死磕动态规划、回溯这些大块头结果面试的时候反而是被双指针这种“基础题”卡了壳。后来我才反应过来这类题考的不是你记不记得住某个奇技淫巧而是你够不够熟练、边界处理得够不够干净。双指针和滑动窗口之所以值得单独拎出来狠狠练是因为它们几乎是面试中“性价比”最高的解题套路。你不需要背复杂的公式不需要推导状态转移方程只需要理解指针移动的逻辑再加上对边界条件的敏锐度就能稳定解出很大一批题。更重要的是这类题目的时间复杂度通常能从暴力解的O(n²)降到O(n)这个优化幅度在面试里是非常加分的亮点。这篇文章我不打算给你列一堆题号然后说“你们自己去刷”而是想把双指针和滑动窗口的底层逻辑拆开揉碎用我实际刷题时踩过的坑、总结出来的套路帮你建立一套可以直接“抄作业”的思维框架。无论你是刚入门的小白还是刷了几百题但总觉得不够系统的老手这篇文章都值得你花二十分钟认真读完。2. 双指针的三种骨架左右、快慢、相向2.1 左右指针最常用的“同向移动”模式左右指针最常见的应用场景是处理“有序数组”或“字符串子串”类问题。两个指针都从数组头部出发一个走得快一个走得慢或者一个从头、一个从尾按条件交替移动。这种模式的核心思想是通过两个指针的协作把“双重循环”的暴力枚举压缩成一次线性扫描。举个例子最经典的“最长无重复子串”问题给你一个字符串让你找出不含有重复字符的最长子串的长度。如果暴力做你要枚举所有子串、再对每个子串检查有无重复字符复杂度直接到O(n³)。但用左右指针维护一个窗口右指针不断向右扩展遇到重复字符时左指针才向右收缩整个过程每个字符最多被访问两次时间复杂度和空间复杂度都好看得多。我第一次写这题的时候犯了个蠢以为滑动窗口就是简单地把窗口起点往后挪一位就行结果很多测试用例过不了。后来才意识到左指针收缩时必须把窗口内被“挤出去”的那个字符从记录中移除比如用一个集合或者计数器来实时维护当前窗口的字符状态。这个看起来是细节其实就是这类题的灵魂。2.2 快慢指针链表题的亲爹快慢指针最出名的应用是检测链表是否有环快指针每次走两步慢指针每次走一步如果存在环两者必然在某处相遇。这个思路在“环形链表”“寻找链表中间节点”“删除链表倒数第N个节点”等题目中都有变体。快慢指针的好处在于你不需要额外的空间去记录访问过的节点空间复杂度能保持在O(1)这在链表场景下是非常大的优势。我记得自己最开始看到“快慢指针”这个名词时还挺迷惑的心想这不就是一个走路快一个走路慢吗但真正上手之后才发现它妙得很快慢指针不仅能判断环还能找到环的入口。方法是在第一次相遇后让其中一个指针从头开始走另一个从相遇点继续走两者每次各走一步再次相遇的位置就是环的入口。这里面的数学证明先不展开但你要是自己动手画几个例子会发现确实很神奇。顺便提一嘴快慢指针用在数组场景时经常用来做“原地去重”或者“移除元素”。比如给你一个有序数组让你原地删除重复元素让每个元素只出现一次返回新的长度。很多解法用到的就是快慢指针快指针遍历整个数组慢指针指向“下一个不重复元素应该放的位置”每次快指针发现一个和慢指针指向位置不同的值就把它复制到慢指针后面。这样一轮遍历下来既完成了去重又没有额外开空间。2.3 首尾相向指针二分法的亲戚首尾相向对撞指针最经典的场景就是“两数之和有序数组”一个指针指向数组开头一个指针指向数组末尾如果两指针指向值的和大于目标值右指针左移小于目标值左指针右移等于目标值直接返回。这个思路的时间复杂度也是O(n)而且对于有序数组来说它是二分查找之外的另一个必备手段。对撞指针的另一个高频应用是“三数之和”先对数组排序然后固定一个数剩下两个数用对撞指针去找。这道题如果不用对撞指针你很容易写出一个三重循环然后被时间复杂度教做人。但一旦用了排序加对撞指针整体复杂度就降到了O(n²)虽然还不是最优但已经是面试里能接受的答案了。这里要特别提醒一点对撞指针经常会碰上去重的问题。比如三数之和如果数组里有重复元素你不去重的话会得到一堆重复的三元组。我当时就在这里吃过亏——写出来的答案老是带着重复组合后来才知道要在固定数和左右指针移动时分别做一次去重判断而且去重的条件要写在找到一个答案之后不是找到一个答案之前这个顺序搞反了也很容易出错。3. 滑动窗口的临界点问题什么时候收缩、什么时候更新答案3.1 定长窗口先扩充再滑动定长滑动窗口的套路其实很固定先让右指针走完第一个窗口的长度然后右指针每前进一步、左指针就跟进一步始终保持窗口长度不变。这种模式最适合处理“固定长度子数组的最大值/最小值/平均值”这类问题。比如给你一个数组和一个窗口大小k让你求所有长度为k的连续子数组的最大和定长窗口就是最好的解法。我自己的习惯是先写一个循环把前k个元素的和算出来作为初始状态然后再用一个从k到数组末尾的循环每次加上新元素、减去移出的元素、更新最大值。这个过程看起来简单但有几个坑一是要搞清楚循环的下标范围特别是左右指针分别指向什么位置二是窗口滑动时更新结果的时机要放在“滑动完成后”否则容易漏掉初始窗口的答案。我之前写“滑动窗口最大值”这道题时就是因为更新答案的位置放错了结果白折腾了半个小时。3.2 可变窗口关键在“满足条件”的判定可变窗口比定长窗口稍微难一点因为窗口的大小不是固定的你需要根据题目条件来决定什么时候扩大窗口、什么时候收缩窗口。这类题的核心是维护一个“当前窗口状态”比如字符出现的次数、区间内元素的和、不同字符的个数等然后根据这个状态是否满足题目要求来决定指针怎么移动。最典型的例子是“最小覆盖子串”给你一个字符串s和一个字符串t让你在s中找到包含t全部字符的最小子串。这道题的精髓在于右指针不断向右扩展窗口直到窗口“覆盖”了t中所有字符然后左指针开始收缩每次收缩前先记录当前窗口长度和起始位置一旦收缩后不再满足覆盖条件就停下来让右指针继续扩展。整个过程就好像你在一堆杂物里找东西先扒拉开一大片确认找到了所有需要的物品之后再小心地往回收直到再收就会丢掉某个必需品为止。这类可变窗口还有个共同难点怎么高效判断窗口状态是否满足条件。最常见的做法是用一个哈希表记录字符需求次数再用一个变量记录“还有多少个字符种类没有满足数量要求”。注意不是记录“还有多少个字符没满足”而是记录“还有多少种字符没满足”这个差别很关键。我最初写这道题时一直用“每个字符还差几个”直接判断结果每次都要遍历整个哈希表时间复杂度直接爆炸。后来改成用一个needCount变量来计数每次更新字符计数时同步维护这个变量效率一下就上来了。4. 常见题型图谱与速查表4.1 直接套模板的经典题我把滑动窗口和双指针常见题型做一个分类速查表方便你在刷题时对号入座。这张表不是让你死记硬背而是希望你看到题目特征后能快速定位到对应的解题框架。题目特征推荐思路典型代表核心注意点有序数组找两数之和首尾相向指针两数之和 II注意下标从1开始LeetCode风格找最长无重复子串滑动窗口可变无重复字符的最长子串左指针收缩时记得移除字符记录找覆盖子串滑动窗口可变最小覆盖子串用needCount计数而不是遍历哈希表固定窗口最大值滑动窗口定长滑动窗口最大值维护单调递减双端队列链表是否有环快慢指针环形链表快指针每次走两步不要越界有序数组去重快慢指针删除有序数组中的重复项慢指针指向待写入位置连续子数组最大和滑动窗口定长子数组最大平均数 I初始窗口单独处理找所有字母异位词滑动窗口定长找到字符串中所有字母异位词窗口长度固定只比较字符计数数组4.2 需要一点变形的进阶题有些题表面上看不出来是双指针或滑动窗口但只要你稍加分析就能发现它们的本质。比如“移动零”要求把数组中的所有0移动到末尾同时保持非零元素的相对顺序。这题最快的解法就是用快慢指针慢指针指向“下一个非零元素应该放的位置”快指针一碰到非零元素就和慢指针交换。很多人在面试时遇到这题会先去想排序或者额外开数组但其实快慢指针一行交换就解决了。再比如“接雨水”这道经典难题很多人觉得必须用动态规划或单调栈但其实双指针也能做。思路是维护左右两个指针以及左右两侧的最大高度。每次比较左右最大高度哪边矮就先处理哪边因为矮的那侧的雨水量已经可以由当前最大高度决定了。这种解法每次移动一个指针整体遍历一次数组空间复杂度只有O(1)比动态规划的O(n)空间更好。还有“最长湍流子数组”这类看起来跟滑动窗口没什么关系的题其实也可以用可变窗口来解决。只要你意识到“湍流”本质是一个交替升降的局部模式然后让右指针不断扩展、左指针在违反模式时跳到合适的位置即可。如果你练多了这类变形题会觉得自己的“题感”有了质的提升。所谓题感其实就是看到题目条件时能迅速把它映射到已经熟练的框架上。5. 刷题验收清单与实战建议5.1 容易翻车的高频细节这里我整理了一份自己刷题过程中总结出的高价值细节清单每条都是血泪教训换来的指针移动的先后顺序极容易出错。很多情况下你应该先移动右指针再更新答案但有些题恰恰相反要先把当前窗口状态记录为答案再移动左指针。这个顺序问题没有万能答案只能靠多练多总结。边界条件写错是最常见的低级错误。比如循环条件是left right还是left right这个问题在二分查找、对撞指针、快慢指针里都会遇到。我的习惯是先在纸上画出几个典型用例用具体数字去模拟指针走一遍确认边界无误再写代码。字符串类题目中字符计数数组往往比哈希表快一个数量级。如果题目明确说明只包含小写字母或ASCII字符直接用长度为26或128的数组做计数器性能远好于用HashMap。滑动窗口的初始状态很重要。我见过很多人在第一个窗口还没处理完就开始进入滑动循环导致漏掉第一个窗口的答案。建议把“处理第一个窗口”和“滑动后续窗口”分开写虽然代码稍长但不容易出错。当你用一个变量维护“窗口内是否满足条件”的计数时增减计数的时机必须和修改哈希表/数组的时机严格同步否则会出现“计数和实际状态不一致”的诡异bug这种bug极难排查。5.2 我在实际刷题中的心得刷双指针和滑动窗口这块我个人最大的体会是不要贪多每个类型挑三五道代表性的题吃透比做一百道囫囵吞枣的题有用得多。我也见过很多同学天天打卡几十道题最后遇到新题照样卡壳原因就是他们只记住了某个题的解法而不是把题型背后的思考方式内化成自己的东西。我的做法是这样每道题做完之后尝试修改题目条件比如把“最长”改成“最短”把“字符串”改成“数组”把“无重复”改成“最多重复两次”然后看看原来的框架还能不能解。如果能解但逻辑有小改动说明你是真的理解了如果完全不知道从哪里下手说明你还没吃透这道题。这个方法听起来有点费时间但对能力的提升非常明显。还有一个特别值得推荐的实战技巧把“窗口缩小时是否更新答案”作为一道题的重要分类依据。有些题和“最长”相关更新答案通常在窗口扩大后有些题和“最短”相关更新答案则是在窗口收缩过程中。把这个点想清楚了很多题的解题路径就自动浮现出来了。提示刷题时不要只看题解一定要自己先动手写哪怕写不出来、看了解析也要亲手把代码敲一遍。看懂了和会写了是完全两码事。我自己写完代码后还会做一件事把代码删掉第二天重新默写一遍。如果能流畅写出来才算真正过关。最后再分享一个小技巧如果你想用这套框架去应付面试建议把“快慢指针找链表中间节点”“滑动窗口求最长无重复子串”“对撞指针求两数之和”这三道题练到闭着眼睛都能写出来。它们分别是三种双指针骨架中最基础的题只要这三道你能写得又快又对面试官对你的基础能力基本就有底了。
阅读完成 · 觉得有帮助？
