文档技术博客教程【免费下载链接】weekly前端精读周刊。帮你理解最前沿、实用的技术。项目地址https://gitcode.com/GitHub_Trending/we/weekly点击查看免费下载滑动窗口双指针是数组、字符串、链表类问题中性价比极高的基础算法它通常是一类有规律数组问题的最优解甚至能在动态规划也可解的场景下取得更优效率。本篇技术指南以「前端精读周刊」算法系列 《算法 - 滑动窗口》 为骨架从两数之和一路讲到接雨水覆盖碰撞指针、快慢指针、按值驱动与多段窗口四类套路并给出每个题目的可运行 TypeScript 实现最后结合仓库中的 《算法题 - 最小覆盖子串》 实战文档展示滑动窗口在高难度题目中的完整落地。读完你将掌握「何时用双指针、窗口怎么滑、以及如何证明滑动不重不漏」这套完整的解题方法论。滑动窗口的本质双指针与窗口滑动窗口使用双指针解决问题所以一般也叫双指针算法因为两个指针间形成一个窗口。两个指针通常命名为left/right或slow/fast它们之间的区间就是“窗口”通过不断调整指针位置让窗口在数组或链表上滑动从而在不重复遍历的前提下覆盖所有候选解窗口滑动的过程中往往只需要维护窗口内的“增量信息”如当前和、字符集合、计数表就可以快速判断窗口是否满足题目条件。双指针并不局限在数组问题链表场景的“快慢指针”也属于双指针的范畴。快慢指针滑动过程中本身就会产生一个窗口当窗口收缩到某种程度可以得到一些结论例如判断链表是否有环、寻找链表中点等。因此掌握滑动窗口非常基础且重要。值得一提的是滑动窗口与动态规划经常出现在同一道题的备选方案里。原文档开篇就点明如果一个数组问题可以用动态规划解但又可以使用滑动窗口解决那么往往滑动窗口的效率更高。这一点与仓库中 《算法 - 动态规划》 相互印证——动态规划靠缓存与状态转移方程消除重复子问题而滑动窗口直接利用“连续区间”的结构用指针的单调移动保证每个元素最多进出窗口一次从而做到 O(n)。两者并不冲突窗口问题若连续、可滑动优先滑动窗口若存在复杂的决策分支、需要枚举组合则考虑动态规划。何时该用双指针三条判断准则双指针本质上是暴力算法的优化版因此可以先从暴力视角切入再判断是否可优化。原文档给出三条实用准则如果题目较为简单且是数组或链表问题往往可以尝试双指针是否可解如果数组存在规律如有序、递增、连续子区间等可以尝试双指针如果链表问题限制较多比如要求 O(1) 空间复杂度解决也许只有双指针可解。也就是说当一个问题比较有规律、较为简单、或较为巧妙时可以尝试双指针滑动窗口解法。下文的所有例题本质上都是在这三条准则指导下“从暴力走向双指针”的推演。单指针热身两数之和哈希表加速两数之和是一道简单题实际上和滑动窗口没什么关系但为了引出三数之和先讲这道题。题目如下给定一个整数数组nums和一个整数目标值target请你在该数组中找出和为目标值target的那两个整数并返回它们的数组下标。你可以假设每种输入只会对应一个答案但是数组中同一个元素在答案里不能重复出现。暴力解法就是穷举所有两数之和发现和为target即结束显然这种做法很慢。由于可以用空间换时间又只有两个数可以对题目进行转化通过一次遍历将nums每一项都减去target即记录target - num用哈希表map加速查询将每一项的target - num作为 key如果后面任何一个num作为 key 能在map中找到则得解且上一个数的原始下标存在map的 value 中。这样仅需遍历一次时间复杂度为 O(n)代码如下function twoSum(nums: number[], target: number): number[] { const map: Recordnumber, number {}; for (let i 0; i nums.length; i) { // 当前 nums[i] 是否就是之前某个 target - num if (map[nums[i]] ! undefined) { return [map[nums[i]], i]; } // 把 target - nums[i] 存入 map等待后面的数来命中 map[target - nums[i]] i; } return []; }之所以先讲这道题是因为它是单指针——只有一个指针在数组中移动并配合哈希表快速求解。对于稍微复杂的问题单指针就不够了需要用双指针解决一般来说不会用到三个或以上指针那复杂点的题目就是三数之和了。排序让窗口可滑三数之和三数之和是一道中等题别以为只是两数之和的加强版其思路完全不同。题目如下给你一个包含n个整数的数组nums判断nums中是否存在三个元素a、b、c使得a b c 0请你找出所有和为0且不重复的三元组。由于超过了两个数不能像两数之和那样用单指针求解了因为即便用了哈希表存储也会在遍历时遇到“两数之和”的问题而哈希表方案无法继续嵌套使用即无法进一步降低复杂度。为了降低时间复杂度我们希望只遍历一次数组这就需要数组满足一定条件我们才能用滑动窗口所以先对数组进行排序。使用快排的时间复杂度为 O(nlogn)虽然超出了两数之和但题目更复杂这个牺牲无法避免。假设从小到大排序拿到一个递增数组后经典滑动窗口方法就可用了创建两个指针left与right通过不断修改它们让窗口在数组间滑动每次遍历的起始点i如果nums[i] 0则直接跳过因为数组排序后是递增的后面的和只会永远大于 0否则进行窗口滑动先形成三个点[i, i1, n-1]保持i不动不断包夹后两个数字只要它们的和大于 0就将第三个点左移数字会变小否则将第二个点右移数字会变大。第二个和第三个数构成的区间就是滑动窗口。可以拿一个全局变量记录窗口内数字的和这样right - 1只要减去nums[right]、left 1只要加上nums[left 1]即可快速拿到新和。同时题目要求“不重复的三元组”因此遇到与上一个相同的元素要跳过。完整实现如下function threeSum(nums: number[]): number[][] { const result: number[][] []; nums.sort((a, b) a - b); for (let i 0; i nums.length - 2; i) { // 递增数组nums[i] 0 时后面只会更大直接跳出 if (nums[i] 0) break; // 跳过重复的起点避免重复三元组 if (i 0 nums[i] nums[i - 1]) continue; let left i 1; let right nums.length - 1; while (left right) { const sum nums[i] nums[left] nums[right]; if (sum 0) { right--; // 和大于 0右指针左移让数字变小 } else if (sum 0) { left; // 和小于 0左指针右移让数字变大 } else { result.push([nums[i], nums[left], nums[right]]); // 跳过重复值后继续寻找其他组合 while (left right nums[left] nums[left 1]) left; while (left right nums[right] nums[right - 1]) right--; left; right--; } } } return result; }时间复杂度是 O(n²)因为存在两次遍历忽略快排较小的时间复杂度 O(nlogn)。推广到 N 数之和为什么排序成本可以忽略四数之和和三数之和完全一样除了要求变成四个数首先还是排序然后双重递归即确定前两个数不变不断包夹后两个数后两个数就是i1和n-1算法和三数之和一样最终时间复杂度为 O(n³)。那么 N 数之和N 2都可以采用这个思路解决。为什么没有更优的方法呢原文档给出两点分析无论几数之和快排一次时间复杂度都是固定的所以沿用三数之和的方案其实占了排序算法的便宜滑动窗口只能用两个指针进行移动而没有“三指针但保持时间复杂度不变”的窗口滑动算法存在。所以对于 N 数之和通过排序付出 O(nlogn) 之后可以用滑动窗口将 2 个数的时间复杂度优化为 O(n)整体时间复杂度是 O(N-1 个 n)。而最小的时间复杂度 O(n²) 比 O(nlogn) 大所以总是可以忽略快排的时间复杂度——三数之和是 O(n²)四数之和是 O(n³)依此类推。从最简单的两数之和到三数之和、四数之和我们已经跨入了滑动窗口的门槛。本质上是利用排序后数组有序的特性让我们在不用整体遍历数组的前提下可以对窗口进行滑动——这是滑动窗口算法的核心思想。不重不漏无重复字符的最长子串无重复字符的最长子串是一道中等题题目如下给定一个字符串请你找出其中不含有重复字符的最长子串的长度。由于最长子串是连续的所以显然可以考虑滑动窗口解法。设定left和right并用一个哈希 Set 记录窗口中存在过的元素在过程中记录最大长度尝试right右移把新字符加入窗口如果右移过程中发现出现重复字符则left右移从窗口中移除左侧字符直到消除这个重复字符为止。代码如下function lengthOfLongestSubstring(s: string): number { const window new Setstring(); let left 0; let max 0; for (let right 0; right s.length; right) { // 出现重复字符时left 右移直到窗口内不再包含 s[right] while (window.has(s[right])) { window.delete(s[left]); left; } window.add(s[right]); max Math.max(max, right - left 1); } return max; }解法并不难但关键问题是为什么用滑动窗口遍历一次就可以做到不重不漏即为什么这道题时间复杂度只有 O(n)想明白两个问题即可由于子串是连续的既然不存在跳跃的情况只要一次滑动窗口内能包含所有解就涵盖了所有情况一次滑动窗口内不包含什么我们只将right右移且出现重复后尝试将left右移到不重复后right再继续右移这忽略了出现重复后right左移的情况。重点看第二个问题如果abcd这四个连续字符不重复那么left右移后bcd也显然不重复所以此时就可以将right右移形成bcda的窗口继续找下去而不需要尝试bc这种情况——因为bc虽然不重复但长度更短一定不是最优解。通过这个例子可以看到滑动窗口如何缩小窗口范围其实不难但更要注重的是背后对于“为什么可以用滑动窗口”的思考滑动窗口有没有做到不重不漏。如果没有想清楚可能整个思路都错了。快慢指针以相对速度滑动窗口前面说的都是“缩小窗口”这种比较单一的脑回路其实双指针构成的滑动窗口不一定都那么正常滑一种有意思的场景是快慢指针——以相对速度决定窗口如何滑动。经典的题目有环形链表、删除有序数组中的重复项。环形链表为什么是 1 步与 2 步环形链表是一道简单题题目如下给定一个链表判断链表中是否有环。如果不是进阶要求空间复杂度 O(1)可以在遍历时稍稍“污染”一下原始链表例如把访问过的节点标记起来这样总能发现是否走了回头路。但要求空间开销必须是常数就不得不考虑快慢指针。快慢指针需要知识迁移的能力想象学校开运动会每次都有一个跑得最慢的同学慢到被最快的同学追了一圈。操场不就是环形链表吗只要有人跑得慢就会被跑得快的追上追上不就是相遇了吗所以快慢指针分别跑只要相遇则判定为环形链表否则不是环形链表且一定有一个指针先走完。function hasCycle(head: ListNode | null): boolean { let slow head; let fast head; while (fast ! null fast.next ! null) { slow slow!.next; // 慢指针每次走 1 步 fast fast.next.next; // 快指针每次走 2 步 if (slow fast) { return true; } } return false; }那么细枝末节就是优化效率了慢指针到底慢多少呢有人会说运动会上跑步慢的人如果想被快的人追上最好就不要跑。对但环形链表问题中链表不是操场可能只有某一段是环也就是跑步慢的人至少要跑到环里才可能与跑得快的人相遇但跑得慢的人又不知道哪里开始成环这就是难点。为什么快排用二分法而不是三分法为什么每次中间来一刀可以最快排完原因是二分可以用最小的“深度”将数组切割为最小粒度。同理快慢指针中慢指针要想被尽快追上速度可能最好是快指针的一半。从逻辑上分析如果慢指针太慢可能大部分时间都在进入环形之前的位置转悠快指针虽然快但永远在环里跑所以总是无法遇到慢指针——慢指针不能太慢如果慢指针太快几乎速度和快指针一样就像两个运动员互不相让地争夺第一一样真想相遇估计得连续跑几个小时——慢指针也不能过快。所以慢指针只能取折中的一半速度。但用一半的慢速真的能最快相遇吗不一定。举一个例子假设链表是完美环形一共有 [1,6] 共 6 个节点慢指针一次走 1 步、快指针一次走 2 步位置序列为2,3 → 3,5 → 4,1 → 5,3 → 6,5 → 1,1共走 6 步相遇但快指针一次走 3 步呢位置序列为2,4 → 3,1 → 4,4只要 3 步。这么说一般速度不一定最优其实不是的计算机在链表寻址时节点访问的消耗也要考虑进去。后者虽然看上去更快但访问链表next的次数更多对计算机来说还不如第一种快。所以准确来说不是“快指针比慢指针快一倍速度”而是慢指针一次走一步、快指针一次走两步最优因为相遇时总移动步数最少。链表中点快慢指针的经典推论快指针是慢指针速度的 2 倍当快指针到达尾部时慢指针的位置就是链表中点function middleNode(head: ListNode | null): ListNode | null { let slow head; let fast head; while (fast ! null fast.next ! null) { slow slow!.next; fast fast.next.next; } return slow; }链表中倒数第 k 个节点链表中倒数第 k 个节点是一道简单题题目如下输入一个链表输出该链表中倒数第k个节点。为了符合大多数人的习惯本题从1开始计数即链表的尾节点是倒数第1个节点。这道题就是判断链表中点的变种让快指针先走k步然后快慢指针同步前进当快指针到达末尾时慢指针就指向倒数第k个节点function getKthFromEnd(head: ListNode | null, k: number): ListNode | null { let slow head; let fast head; // 快指针先走 k 步 for (let i 0; i k; i) { fast fast!.next; } // 快指针到末尾null时慢指针正好是倒数第 k 个 while (fast ! null) { slow slow!.next; fast fast.next; } return slow; }这里注意一下数数别数错了即可快指针先走k步后两者间距恒为k当快指针越过尾节点走到null时慢指针所处位置即倒数第k个节点。按值驱动删除有序数组中的重复项删除有序数组中的重复项是一道简单题题目如下给你一个有序数组nums请你原地删除重复出现的元素使每个元素只出现一次返回删除后数组的新长度。这道题要求原地删除重复元素并返回长度所以只能用快慢指针。但怎么用呢快多少慢多少——与前面题目不同这里的“快慢”不是预设好的而是根据遇到的实际数字来判断。注意变量命名也有讲究同样是双指针问题有的是left/right有的是slow/fast重点在于用何种方法移动指针。做法是让fast扫描完全表把所有不重复的值挪到一起让slow和fast初始都指向 index 0由于是有序数组重复值一定连在一起所以可以让fast直接往后扫描只有遇到和slow不同的值才把其写到slow1的位置然后slow自增继续扫描直到fast走到数组尾部结束。function removeDuplicates(nums: number[]): number { if (nums.length 0) return 0; let slow 0; for (let fast 1; fast nums.length; fast) { // fast 遇到与 slow 不同的值才把其挪到 slow1slow 前进 if (nums[fast] ! nums[slow]) { slow; nums[slow] nums[fast]; } } // slow 从 0 计数数组新长度为最后一个不重复元素下标 1 return slow 1; }可以看到这道题对于慢指针要如何“慢”其实是根据值来判断的如果fast的值与slow一样那么slow就一直等着——因为相同的值要被忽略掉让fast继续走就是在跳过重复值。移动规则的巧妙设计盛最多水的容器盛最多水的容器是一道中等题题目如下给你n个非负整数a1, a2, ..., an每个数代表坐标中的一个点(i, ai)。在坐标内画n条垂直线垂直线i的两个端点分别为(i, ai)和(i, 0)。找出其中的两条线使得它们与x轴共同构成的容器可以容纳最多的水。为什么说这是一道双指针题目因为容纳水的体积可以简化为“长乘宽”长度就是选取的两个柱子的间距宽就是其中最短柱子的高度。问题是虽然柱子间距越远长度越大但宽度不一定最大一眼是看不出最优解的所以还是得多次尝试。怎样用最少的尝试次数又不重不漏定义left、right两个指针分别指向0与n-1首尾两个位置此时长度最大柱子间距离最远。接下来尝试别的柱子试哪个呢较长的那个如果新的柱子更短那么宽度更短了如果新的更长也没用因为较短的决定了水位。较短的那个如果新的较长那么才有机会让整体体积更大。所以每次移动较短的那根柱子并计算一次体积最后当两根柱子相遇时结束过程中最大体积就是全局最大体积function maxArea(height: number[]): number { let left 0; let right height.length - 1; let max 0; while (left right) { const area Math.min(height[left], height[right]) * (right - left); max Math.max(max, area); // 移动较短的那根柱子才有机会让水位变高 if (height[left] height[right]) { left; } else { right--; } } return max; }这道题双指针的移动规则比较巧妙重点不在于是否会运用滑动窗口算法而是能否找到移动指针的规则。你可能会问为什么两个指针要定义在最两端而非别的地方因为这样就无法控制变量了如果指针选在中间位置那么指针外移时柱子的间距与柱子长度同时变化很难找到一条完美路线我们移动较短的柱子是因为较短的柱子确定了最低水位改变它可能让最低水位变高但如果间距也在同时变化移动较短还是较长的柱子哪个更优就说不准了。说实话这种方法不太容易想到需要多找几种选择尝试才能发现。算法如果按照固定套路就能推导出来也就没有难度了所以要接受这种思维跳跃。多段滑动窗口接雨水接雨水是一道困难题题目如下给定n个非负整数表示每个宽度为1的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。与盛雨水不同接雨水看的是整体要算出能接的所有水的数量。相比上一道题这道题还算比较好切入因为从左到右计算即可。思考发现只有产生了凹槽才能接到雨水而凹槽由它两边最高的柱子决定。那什么范围算一段凹槽呢显然凹槽是可以明确分组的一个凹槽无法被分割为多个凹槽就像你看水坑一样无论多少、多深的坑在一起总能一个一个数清楚。所以从左到右开始数用滑动窗口的办法每个窗口就是一个凹槽窗口起点left就是左边第一根柱子如果直接相邻的右边柱子更高或一样高那从它开始向右看根本无法接雨水直接抛弃left如果直接相邻的右边柱子更矮那就有产生凹槽的机会继续往右看如果右边一直都更矮那也接不到雨水如果右边出现一个高一些的就可以接到雨水。记录最左边柱子高度右边柱子的结束判断条件是“遇到一个与最左边一样高的柱子”——因为一个凹槽能接多少水取决于最短的柱子。当然如果右边没有柱子了虽然比最左边低一点但只要比最深的高也算一个结束点。一旦遇到凹槽结束点left就会更新开始新的一轮凹槽计算所以这道题存在多个滑动窗口。按原文思路实现的代码如下function trap(height: number[]): number { let total 0; let left 0; while (left height.length - 1) { // 右边相邻柱子更高或一样高无法形成凹槽直接跳过 if (height[left 1] height[left]) { left; continue; } const leftHeight height[left]; let right left 1; let maxRight right; // 记录右边最高柱子的位置 let maxRightHeight height[right]; // 向右扫描要么找到与 leftHeight 一样高的柱子要么记录右边最高点 while (right height.length height[right] leftHeight) { if (height[right] maxRightHeight) { maxRightHeight height[right]; maxRight right; } right; } // 结束点优先取第一个 leftHeight 的柱子否则取右边最高点 let end right; if (end height.length) { end maxRight; } // 计算 [left, end] 区间内的水量 const waterLevel Math.min(leftHeight, height[end]); for (let i left 1; i end; i) { if (height[i] waterLevel) { total waterLevel - height[i]; } } left end; // 开启下一段凹槽 } return total; }这种“分段凹槽”的写法直观地还原了原文思路窗口按凹槽天然分组、逐段推进、逐段结算。不过它存在重复扫描的情况最坏时间复杂度为 O(n²)。工程中更常用的是双指针从两端向中间收拢的 O(n) 解法——左右两端同时维护“当前左侧最高柱”与“当前右侧最高柱”哪边柱子矮就从哪边结算水量并收拢指针正确性依据是某一侧能存多少水只取决于该侧已知的最高柱function trap(height: number[]): number { let left 0; let right height.length - 1; let leftMax 0; let rightMax 0; let total 0; while (left right) { leftMax Math.max(leftMax, height[left]); rightMax Math.max(rightMax, height[right]); if (height[left] height[right]) { total leftMax - height[left]; left; } else { total rightMax - height[right]; right--; } } return total; }两种写法对经典的[0,1,0,2,1,0,1,3,2,1,2,1]用例都能算出 6。从这道题可以看出滑动窗口题型相当灵活不仅判断条件因题而异窗口数量也可能有多个。仓库实战最小覆盖子串中的滑动窗口除了上述例题仓库算法系列还收录了滑动窗口的高阶实战——《算法题 - 最小覆盖子串》。题目是给你一个字符串s、一个字符串t返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串则返回空字符串。对于t中重复字符寻找的子字符串中该字符数量必须不少于t中该字符数量。该题首先要排除动态规划字符串匹配场景不适合并根据连续子串特性第一时间想到滑动窗口可以覆盖所有可能性。核心思路是如果当前字符串覆盖t左指针右移否则右指针右移——窗口先右移判断是否满足条件满足后不一定是最优再让左指针继续右移寻找更短答案。真正的难点是如何高效判断当前窗口内字符串是否覆盖t。文档对比了三种方案对每个字符做一个计数器再加一个总计数器——有漏洞总计数器不包含字符类型信息比如连续匹配 100 个b时总计数器一直在加但此时其实缺的是c二进制位图如 26 个 01 表示 26 个字母——不可行因为每个字符出现的次数会超过 1不是布尔类型notCoverChar方案文档推荐用一个Setstring记录“未 ready 的字符”。所谓 ready即该字符在当前窗口内出现的次数 该字符在t中出现的次数。右指针右移时对应计数增加达到t的要求后从notCoverChar移除左指针右移时对应计数减少低于要求则重新放回notCoverChar。当notCoverChar为空即窗口覆盖t此时记录最短结果。仓库文档 《算法题 - 最小覆盖子串》 中给出了完整的 TypeScript 实现滑动窗口主体见文档中minWindow函数从暴力 O(n²) 到滑动窗口 O(n)是“先确认滑动窗口可行、再设计高性能窗口内判断”的完整实战范例建议配合本篇一起阅读。总结滑动窗口本质是双指针的玩法不同题目有不同的套路从最简单的按规律包夹到快慢指针再到无固定套路的因题而异的特殊算法碰撞指针按规律包夹一般针对排序好的数组可以一步一步判断或配合二分法判断不用根据整体遍历来判断效率自然高快慢指针也有套路可循但具体快多少、慢多少可能具体场景要具体看——环形链表中“慢 1 步、快 2 步”之所以最优是因为相遇时总移动步数最少删除有序数组重复项中则完全由值驱动无固定套路的滑动窗口如盛最多水的容器、接雨水就要根据题目仔细品味移动指针的规则与窗口的边界条件。贯穿始终的一条主线是滑动窗口之所以高效是因为它利用连续区间或排序后有序的结构让每个元素至多被访问常数次从而把暴力遍历降为 O(n) 或 O(n²) 以内而每次使用前都要先想清楚窗口移动是否“不重不漏”这是整个思路成立的前提。本文所有例题的实现均可直接运行验证进一步的背景可参考仓库总览 readme.md前端精读周刊的完整文章索引以及 helper.js周刊目录索引的发布辅助脚本。建议按“先判断题目是否适合双指针 → 确定指针移动规则 → 验证不重不漏 → 编码”的顺序练习把上述四类套路内化成自己的解题习惯。赞分享文档技术博客教程【免费下载链接】weekly前端精读周刊。帮你理解最前沿、实用的技术。项目地址https://gitcode.com/GitHub_Trending/we/weekly点击查看免费下载相关推荐Go结构体验证革命告别if-else拥抱声明式validator库Go结构体验证革命告别if else拥抱声明式validator库 还在为Go项目中的数据验证编写繁琐的if else代码吗每次添加新字段都要重复编写验证后端质量保障LeetCode 42 接雨水Trapping Rain Water全解双数组与双指针算法剖析LeetCode 42 接雨水Trapping Rain Water全解双数组与双指针算法剖析 导读 本文围绕 leetcode 仓库中 problems文档教程知识库接雨水Trapping Rain Water从暴力到双指针的四种解法全解析接雨水Trapping Rain Water从暴力到双指针的四种解法全解析 导读 本文基于 hints/trapping rain water.md ht示例工程教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考