1. 算法打卡第20天前缀和、快慢指针与哈希表的联动实战连续打卡第20天今天这组题目信息量非常大——前缀和、二维前缀和、快慢指针、哈希表set、哈希表map一共7道题。光看标签可能觉得是五个独立知识点实际做下来才发现它们之间是环环相扣的前缀和解决的是区间和的快速查询快慢指针解决的是链表/数组中的位置关系哈希表则是这两者背后最常用的辅助工具。这篇文章把我今天的解题思路、踩坑记录和心得一次说清楚适合正在刷题找工作、或者想系统补算法基础的朋友参考。2. 开题前的整体拆解这7道题到底在考什么2.1 五个知识点各自的定位先说前缀和。它的核心思想非常朴素预处理一个前缀和数组preSumpreSum[i]表示原数组前i个元素的和那么任意区间[l, r]的和就等于preSum[r1] - preSum[l]。这一下把O(n)的区间求和降到了O(1)代价是O(n)的预处理空间。今天的前缀和题目里有一维的也有二维的二维的套路是容斥原理sum[i][j] sum[i-1][j] sum[i][j-1] - sum[i-1][j-1] matrix[i-1][j-1]查询子矩阵和时同样用四个角的加减组合。快慢指针通常用在链表题里但今天在数组题里也遇到了变体——原地移除元素这类问题本质上是双指针一个快指针负责遍历找目标一个慢指针负责维护结果数组的写入位置。快慢指针在同向遍历时的核心逻辑是两个指针之间保持某种距离关系这个距离关系往往就是题目的隐藏条件。哈希表的set和map今天都有出现。set的关键特性是元素唯一且去重快常用于判重、去重、记录是否出现过map则是键值对存储适合记录某个值对应的下标、某个前缀和出现的次数这类映射关系。做题时选set还是map取决于你需要的是一般性存在判断还是需要同时记录关联信息。2.2 7道题的组合规律今天的7道题不是随机拼盘仔细看会发现有一条隐藏主线都是关于如何快速获得区间/子序列的信息以及如何判断位置关系。前缀和类的题目核心是利用preSum把O(n^2)的枚举优化到O(n)或O(n^2)配合哈希表的O(1)查询。快慢指针类的题目核心是利用指针相对位置来避免多余遍历。哈希表类的题目核心往往是把见过的状态存下来避免重复计算。所以今天真正要练的能力不是“背模板”而是学会识别题目背后“空间换时间”的意图。我建议做这类双知识点的题时先自己口头说出“为什么用这个数据结构”再动手习惯之后选题思路会快很多。3. 前缀和一维与二维的完整推导3.1 一维前缀和的标准写法这里的套路我在打卡第5天就整理过但今天仍然用到了。一维前缀和的处理要点定义preSum数组长度为原数组长度1preSum[0] 0遍历原数组preSum[i1] preSum[i] nums[i]区间[l, r]下标从0开始的和 preSum[r1] - preSum[l]。示例代码用我平时最顺手的语言风格写function preSum(nums) { const pre new Array(nums.length 1).fill(0); for (let i 0; i nums.length; i) { pre[i 1] pre[i] nums[i]; } return pre; } function rangeSum(pre, l, r) { return pre[r 1] - pre[l]; }这里有两个细节容易出错一是数组长度要1否则rangeSum右边界会越界二是查询区间和时右边界是r1而不是r。很多新手第一次写前缀和会忘记这两点实际调试时边界报错一眼就能看出来。3.2 二维前缀和的容斥原理推导今天有一道二维矩阵的题。二维前缀和的预处理公式为pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] matrix[i-1][j-1]其中pre[i][j]表示左上角(0,0)到(i-1,j-1)的子矩阵元素和。查询子矩阵(row1, col1)到(row2, col2)的和sum pre[row21][col21] - pre[row1][col21] - pre[row21][col1] pre[row1][col1]这个公式看着像四个数的加减实际就是在做容斥先减掉上面一行之外的部分再减掉左边一列之外的部分但左上角被重复减了两次所以再加回来一次。跟一维前缀和的减法思想完全一致只是维度多了一维容斥公式需要同时考虑行、列两个方向的加加减减。我在纸上推过一遍这个公式强烈建议你也自己动手画一个3×3的小矩阵手动算一遍。纸上推完之后再写代码就不会糊。function NumMatrix(matrix) { const m matrix.length, n matrix[0].length; const pre Array.from({ length: m 1 }, () new Array(n 1).fill(0)); for (let i 1; i m; i) { for (let j 1; j n; j) { pre[i][j] pre[i - 1][j] pre[i][j - 1] - pre[i - 1][j - 1] matrix[i - 1][j - 1]; } } this.pre pre; } NumMatrix.prototype.sumRegion function(row1, col1, row2, col2) { const pre this.pre; return pre[row2 1][col2 1] - pre[row1][col2 1] - pre[row2 1][col1] pre[row1][col1]; };3.3 前缀和哈希表区间问题的最强组合今天有一道题非常典型给一个数组问有多少个连续子数组的和等于k。最朴素的做法是枚举每个起点和终点O(n^2)计算和惨不忍睹。用前缀和preSum之后问题变成有多少对(i, j)满足preSum[j] - preSum[i] k即preSum[i] preSum[j] - k。这时候再用哈希表map记录每个前缀和值出现的次数一边遍历一边查map里是否存在preSum[i] - k的计数累计答案即可。整个过程只需要O(n)时间。function subarraySum(nums, k) { const map new Map(); map.set(0, 1); let sum 0, count 0; for (const num of nums) { sum num; if (map.has(sum - k)) count map.get(sum - k); map.set(sum, (map.get(sum) || 0) 1); } return count; }这里有个很重要的初始化map里要预置preSum0出现1次不然从起点开始的子数组会漏算。这是我踩过的一个坑后面在常见问题里也会说。这个题的思维路径其实是拆解把区间和问题转化为两个前缀和之差再用哈希表做快速配对查找。这正是今天“前缀和哈希表”联动的一个很好的实例。4. 快慢指针同向双指针的两种实战模型4.1 链表去重保留元素只移动慢指针今天快慢指针的题第一个是链表去重。题目要求删除有序链表中重复的元素每个值只保留一个。经典的写法就是快慢指针function deleteDuplicates(head) { if (!head) return head; let slow head, fast head; while (fast) { if (fast.val ! slow.val) { slow.next fast; slow slow.next; } fast fast.next; } slow.next null; return head; }这里的核心逻辑fast每次都往前走发现新值时才让slow动。slow永远指向“结果链表的最后一个位置”fast负责探索。注意最后要把slow.next置为null否则原链表中残留未处理的后半段会多出来。链表题最容易忽略这个收尾动作。4.2 原地移除元素数组上的快慢指针另一个变体是数组题原地移除所有值为val的元素返回新长度。数组上不能像链表那样直接断链但可以用双指针复制覆盖function removeElement(nums, val) { let slow 0; for (let fast 0; fast nums.length; fast) { if (nums[fast] ! val) { nums[slow] nums[fast]; slow; } } return slow; }把nums[fast]的值直接写到nums[slow]相当于维护了一个结果数组的前缀。快指针遍历原数组慢指针作为写入指针。同样的思路可以推广到“移动零”这类题目。快慢指针的核心理解是“慢指针是结果区间的右边界快指针是探索者”在纸上划线模拟几组数据基本就不会再丢状态。4.3 为什么快慢指针往往和哈希表无关但今天会放在一起有意思的是今天编译器把快慢指针和哈希表放在同一个打卡里实际上这两类题目经常在面试题里交替出现链表类的去重/环问题有时可以用set解决比如记录访问过的节点而数组类的去重会用到双指针。做题时可以在大脑里有一条“备选链”如果需要记忆状态就选set/map如果需要原地修改就选双指针。两者并不矛盾很多复杂题目还会同时使用比如“判断链表是否有环”的常规解法是快慢指针但备选方案是哈希表记录访问过的节点。今天这7道题里有三道都是这个混合思路。我的建议是把“快慢指针”和“哈希表”当做一对互补工具来学习不要孤立记忆。这样遇到变种题时会有更多的解题角度。5. 哈希表set和map的使用细节5.1 什么时候用set什么时候用map只需要判断“这个元素有没有出现过”用set。典型场景去重、查重、判环。需要同时记录“元素x关联的下标/次数/值”用map。典型场景两数之和、前缀和统计次数、窗口滑动记录位置。这两个数据结构的核心区别在于“存的值是key本身还是keyvalue”。如果你是老手一眼看到题目里要返回“下标”或者“次数”时就该考虑map如果只问“是否存在”或者“有几个不同数字”set就够用。5.2 set的典型使用场景去重后计数今天有一道题要统计数组中不同数字的个数我直接用setfunction countDistinct(nums) { return new Set(nums).size; }这个写法简洁但要知道它背后的代价O(n)时间、O(n)空间。如果在面试里被追问优化空间可以考虑排序后统计相邻不同值但日常刷题阶段set的简单直接反而是优势不要过早优化。除了去重set也常用于记录“访问过的状态”。比如有些搜索类问题需要判重避免死循环。这里有一个实践小技巧如果使用JavaScriptset在添加对象时会按引用判断若想按内容判断需要先序列化或使用唯一标识这是一个隐藏坑。这道题虽然没考但在真实业务场景里非常常见。5.3 map的使用技巧前缀和配对map今天的高光体现在“和为k的子数组”这道题我们用preSum作为键出现次数作为值。此时map承担了“状态计数器”的角色。具体步骤初始化map键为0值为1遍历数组维护当前前缀和sum每到一个位置检查map里有没有sum-k这个键有则答案累加其计数值更新当前sum的计数值。这个流程里map既保存了历史状态也提供了O(1)的查询。如果不用map而用一个数组存所有前缀和并两两比较时间复杂度就退化为O(n^2)。所以“空间换时间”的模式在这道题上体现得非常充分。另一个map技巧当你需要把数组元素映射到下标时比如“两数之和”思路就是用一次遍历边查边存function twoSum(nums, target) { const map new Map(); for (let i 0; i nums.length; i) { const diff target - nums[i]; if (map.has(diff)) return [map.get(diff), i]; map.set(nums[i], i); } return []; }这种“边遍历边存储”的模式对前向依赖的题目很有效因为不需要第二次遍历空间和时间都很省。5.4 set和map在JS里的底层差异虽然日常只要会用API即可但理解底层能帮你避开大坑。JavaScript里的Set和Map都基于哈希表实现查找、插入、删除平均O(1)。它们的迭代顺序是“插入顺序”这一点和普通哈希表不同但很多时候反而是特性。需要注意Set存储的是值本身不会重复判断两次相同值Map的键可以是任意类型但如果是对象作为键判断依据是引用而非内容在for...of里可以直接解构比如for (const [key, value] of map)。这些细节在刷题时可能用不到但在真实项目中很实用值得记一笔。6. 实操过程全记录7道题从审题到AC6.1 题单概览与我的解题顺序今天的7道题我按由简到难的顺序做一维前缀和基础题直接套模板和为k的子数组前缀和map二维区域和检索二维前缀和链表去重快慢指针原地移除元素数组快慢指针统计不同数字set两数之和map边查边存。先做基础模板题热身再做组合题这样可以保持思路顺畅。实际上我建议刷题时也这样每类知识点先单独做1-2道基础题确认模板掌握再做混合知识点的变式。这样不会在组合题里同时面临“模板不熟”和“思路不清”两个问题。6.2 具体题目的调试过程这里展开讲一道最有收获的“和为k的子数组”。我第一次提交时忘了map初始放0:1结果漏算了从下标0开始的所有子数组。加上后依然WA原来是因为没有在遍历完一个前缀和后更新map计数。我重新梳理流程先查map再更新map。顺序一定不能反反了之后同一位置的前缀和会把区间长度为零的情况也算进去导致多统计。于是固定了“先查后存”的习惯这道题终于AC。二维前缀和的调试我踩了个小坑pre数组的行列长度分别定义为m1和n1后矩阵的行列索引要记得减1。比如pre[i][j]对应matrix[i-1][j-1]的元素。我第一次写成了matrix[i][j]直接导致结果全部错乱。这也是二维前缀和最常见的错误。6.3 时间空间复杂度验收标准每道题我除了AC还会写下时间复杂度和空间复杂度便于对比不同方案。以今天的题为例一维前缀和预处理O(n)查询O(1)空间O(n)二维前缀和预处理O(m×n)查询O(1)空间O(m×n)和为k的子数组O(n)时间O(n)空间两数之和O(n)时间O(n)空间原地移除元素O(n)时间O(1)空间因为直接原地覆盖链表去重O(n)时间O(1)空间。把复杂度写下来可以直观发现“原地类”题目都是O(1)空间而哈希表辅助类题目用O(n)空间换时间。如果面试官追问“能不能优化空间”你心里就有数了。7. 常见问题速查与避坑指南7.1 前缀和的三个经典坑前缀和模板好背但错误率极高。我整理了三类边界忘记1preSum数组长度要是原数组长度1否则rangeSum拿preSum[r1]时越界查询区间右边界写错区间[l, r]的和要preSum[r1] - preSum[l]不是preSum[r] - preSum[l]二维前缀和索引减一pre[i][j]对应matrix[i-1][j-1]初始化循环里一定要减1。我的建议是把模板写熟后再试着手写一遍而不是背代码。边界这种东西背了容易忘自己推导一遍才记得牢。7.2 快慢指针的终止条件链表去重时很多人会忘掉最后一步slow.next null。原因是快指针已经走到链表末尾但慢指针可能还指向链表中部结果尾部残留了未处理节点。补救方法就是在循环结束后显式截断。数组的removeElement相对安全但要确保返回值是slow而不是slow1。快慢指针判环比如环形链表时终止条件是fast fast.next同时非空否则访问fast.next.next时会报空指针。这是非常经典的运行时错误。7.3 哈希表使用中的细节统计次数时用map.get(key) || 0来避免undefined参与加法用set去重对象时按引用判断若要按内容判断需要额外处理两数之和的“边查边存”顺序不能反先查后存避免同一元素被重复使用如果题目要求返回任意一组解map除了记录下标还可以记录值。这些细节在面试手写代码时很容易暴露建议平时写题时就刻意养成习惯。7.4 实战心法如何把多个知识点串起来今天的题目最终要传达的其实是“组合思维”。刷题时不要孤立地做单一知识点应该多问自己面前这道题能不能用其他数据结构或算法解决举个例子“和为k的子数组”用前缀和map但如果把数组改成链表是不是可以用双指针滑动窗口把数组改成矩阵是不是用二维前缀和这样练习你的知识网络会越来越密。另一个实用心法是“五分钟想思路二十分钟动手”。如果一道题想了五分钟还没有一点方向就去看题解看懂后自己再独立写一遍。不要硬磕太久也不要只看不写。今天7道题我全程用时约一个半小时平均每道题十几分钟比较合理。8. 收获总结与后续建议今天这组打卡覆盖了前缀和、二维前缀和、快慢指针、哈希表set和map7道题全部AC。相比单个知识点我收获最大的是“组合使用”的意识前缀和为哈希表提供历史状态哈希表为前缀和提供O(1)配对查找快慢指针则为原地操作提供了一套优雅的框架。我建议后续刷题时把“哈希表前缀和”区间计数类和“快慢指针哈希表”链表类/去重类作为两个专题去集中刷10-20道题直到一看到关键词就能反应出对应数据结构。数据结构的选择有时比算法本身更重要选对了数据结构很多难题的解法会自然浮出水面。最后分享一个小技巧每完成一组题把你在调试中遇到的错误和对应的解决方案记录到一个“错题本”文档里。不要记题解只记错误的模式。下次遇到类似情况翻一翻你会发现很多错误其实是共通的。算法能力的提升很大程度就来自这些细微的积累。