今天是算法打卡第20天周四。说实话刷到一半的时候我明显感觉到难度开始分层了前缀和和二维前缀和考的是预处理的思想快慢指针考的是链表操作的细节而set和map这两块纯粹是看你熟不熟哈希表的套路。今天这7个题刚好把这五个知识点全过了一遍做完之后有种“之前零散的东西终于串起来了”的感觉。这篇就把今天的解法、踩坑和工具使用技巧整理出来适合正在刷题打基础、尤其是卡在区间求和和链表题上的朋友参考。1. 前缀和一次预处理后面所有区间查询都是O(1)1.1 暴力累加为什么会被卡先说说今天的前缀和题。核心场景很简单给你一个数组反复问某个区间 [l, r] 的和是多少。新手第一反应肯定是每次查询就 for 循环从 l 加到 r。这个写法在小数据量下没什么问题但如果数组长度是10^5查询次数也是10^5双层循环就是10^10次运算妥妥超时。前缀和解决的就是这个痛点提前算出一个 prefix 数组prefix[i] 表示原数组前 i 个元素的和。有了这个预处理之后区间 [l, r] 的和直接等于 prefix[r] - prefix[l-1]查询时间复杂度降到 O(1)。这个优化思路本质上是“把重复计算变成一次计算”很多算法题都是这个套路空间换时间预处理换查询。1.2 一维前缀和的模板代码今天第一道题就是最经典的区间和查询。我直接用 C 写模板你们感受一下处理细节#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; vectorlong long arr(n 1, 0); vectorlong long prefix(n 1, 0); for (int i 1; i n; i) { cin arr[i]; prefix[i] prefix[i - 1] arr[i]; } while (m--) { int l, r; cin l r; cout prefix[r] - prefix[l - 1] endl; } return 0; }两个小细节提醒一下。第一数组下标从1开始这样 prefix[l-1] 不会出现负数下标逻辑上也更好写。第二前缀和数组尽量用 long long尤其是元素值和 n 都大的时候int 很容易溢出。我一开始偷懒用 int结果有一组数据直接爆了。1.3 前缀和的三个反向变形一维前缀和不止“区间求和”这一种考法。今天做的另一道题就是变体给你一个数组问有多少个子数组的和等于 k。如果直接用前缀和数组还是要枚举左右端点复杂度 O(n²)。但实际上可以边遍历边统计核心思路是用哈希表记录每个前缀和出现的次数遍历到当前位置 i 时如果 prefix[i] - k 在哈希表里出现过说明存在以 i 结尾的子数组满足和为 k答案加上哈希表里 prefix[i] - k 对应的次数。这个写法把 O(n²) 的枚举优化成 O(n)是前缀和最经典的配合题。我后来复盘时总结出三个变形方向区间求和型、子数组计数型、以及根据前缀和推导差分问题的类型。遇到前缀和题目先想清楚要求“几个区间、是否可预处理、是否有额外条件”再决定用裸前缀和还是前缀和哈希表。1.4 今天踩过的坑今天的坑主要在边界。有一次我写 query 时直接用了 prefix[r] - prefix[l]结果 l1 的时候算出来的结果偏大。原因就是下标从1开始时应该用 prefix[r] - prefix[l-1]。这个错误特别隐蔽因为小数据测试时可能恰好答案正确只有大数据才暴露。建议写完前缀和题目后单独测 l1 和 rn 两个边界这是最容易漏掉的地方。2. 二维前缀和用容斥原理解决矩阵区域求和2.1 从一维到二维为什么会出现减两次二维前缀和今天也安排上了。场景是一个二维矩阵多次查询某个子矩阵的元素和。如果用暴力双重循环每个查询都要 O(n*m)查询一多就又炸了。二维前缀和的定义是s[i][j] 表示从矩阵左上角 (1,1) 到 (i,j) 这个矩形的所有元素之和。递推公式是s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1] a[i][j]为什么减掉 s[i-1][j-1]因为 s[i-1][j] 和 s[i][j-1] 都包含了左上角那块矩形加了两次必须减掉一次。这就是容斥原理在算法里的典型应用。初学者最容易记混的就是这个递推公式我建议直接在纸上画一个 3×3 的矩阵把每个格子的值标出来推一遍比死记公式有效十倍。2.2 二维前缀和的查询公式查询子矩阵时假设左上角是 (x1, y1)右下角是 (x2, y2)结果是sum s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] s[x1-1][y1-1]同样用容斥原理理解总面积减去上面多出来的、减去左边多出来的但左上角被减了两次要再加回来一次。这个公式我每次写之前都会默念一遍因为现场推导容易乱。一道典型的模板题代码是int n, m, q; cin n m q; vectorvectorlong long s(n 1, vectorlong long(m 1, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { int val; cin val; s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1] val; } } while (q--) { int x1, y1, x2, y2; cin x1 y1 x2 y2; cout s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] s[x1-1][y1-1] endl; }2.3 二维前缀和的常见误区二维前缀和常见的三个误区今天我在群里看到好几个刷题的人都在犯第一矩阵的输入坐标是1-indexed还是0-indexed。如果你习惯用0-indexed递推公式里就得单独处理 i0 或 j0 的边界非常容易爆。建议直接用1-indexed省事很多。第二把原矩阵和前缀和矩阵混在一个数组里。原矩阵一旦被覆盖后续查询就无法进行了。建议定义两个独立变量虽然省一点内存但调试时要看原始数据就麻烦了。第三公式中坐标写反。尤其是 (x1-1, y1-1) 这个部分y 和 x 很容易搞混。我写了个小注释放在代码前面提醒自己“行是 x列是 y先更新行再更新列”。3. 快慢指针链表题的“万金油”套路3.1 快慢指针的核心思想和适用场景快慢指针今天也占了两个题。这个技巧的核心是一个指针每次走一步另一个指针每次走两步利用速度差来制造相对位移。最常见的三个用途是判断链表中是否有环寻找链表的中间节点寻找链表倒数第 k 个节点快指针先走 k 步判断链表是否回文配合反转链表。快慢指针看起来简单但实际写起来对空指针的判断要求极高。今天第一道快慢指针题是“判断链表是否有环”模板非常固定bool hasCycle(ListNode *head) { ListNode *slow head, *fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) return true; } return false; }注意循环条件是fast fast-next如果不判断 fast-next下一步访问 fast-next-next 时可能直接空指针崩溃。这个坑我整整踩过两次每次都是数据小没事、数据尾部有奇数个节点时挂掉。3.2 快慢指针的进阶找到环的入口节点今天另一道快慢指针题升级了——不只要判断有没有环还要找到环的入口。这道题需要一点数学推导。假设链表起点到环入口的距离是 a环入口到相遇点的距离是 b环的剩余长度是 c。那么相遇时慢指针走了 ab 步快指针走了 abk(bc) 步k 是快指针比慢指针多绕的圈数。由于快指针速度是慢指针的两倍所以2(ab) abk(bc) ab k(bc) a k(bc) - b这个式子的关键结论是从链表起点开始走 a 步和从相遇点开始继续走 a 步最终会到达同一个位置也就是环的入口。因此算法是先找到相遇点然后把 slow 移回链表头fast 保持在相遇点两个指针每次都走一步再次相遇时就是环的入口。这个证明第一次看可能有点绕但推导一遍之后就记住了。今天我用的代码ListNode *detectCycle(ListNode *head) { ListNode *slow head, *fast head; bool hasCycle false; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) { hasCycle true; break; } } if (!hasCycle) return nullptr; slow head; while (slow ! fast) { slow slow-next; fast fast-next; } return slow; }3.3 快慢指针实操中的几个细节今天这两道题做完我总结了三个实操心得第一快指针步进一定要放在循环体内不能放在循环条件外否则可能出现指针已经是 nullptr 却还要取 next 的问题。第二判断相等用指针本身而不是指针的值链表节点可能值相同但地址不同。第三如果题目要求返回节点而不是 bool务必记住先判断有没有环再处理入口逻辑否则空节点会直接报错。4. 哈希表set去重和存在性判断的正确打开方式4.1 set 适合解决什么问题今天涉及 set 的题目是典型的“判断数组中是否有重复元素”。set 本身就是一个只存储不重复元素的数据结构底层是平衡树std::set或哈希表std::unordered_set所以我们只需要把它当作“一件衣服穿过没有”的记号牌每次往里面丢一个元素如果丢不进去就说明这个元素之前已经出现过。这个思路配合遍历一次数组时间复杂度 O(n)用起来非常顺手。今天这道题我直接用了 unordered_setbool containsDuplicate(vectorint nums) { unordered_setint st; for (int num : nums) { if (st.count(num)) return true; st.insert(num); } return false; }4.2 这个技巧好用在哪直接用插入返回值很多新手写 set 去重时习惯先 count 再 insert但实际上 insert 函数本身就返回一个 pairfirst 是指向元素的迭代器second 是 bool表示是否插入成功。所以更简洁的写法是if (!st.insert(num).second) return true;这个写法少了一次查表代码也更短。今天在写这道题的时候我特意试了一下两种写法实测数据量到 10 万级别时差别不大但写法更干净、也更能体现对 API 的熟悉程度。4.3 一个很隐蔽的坑哈希值计算需要提醒的是unordered_set 依赖哈希函数对 int、string 这些内置类型没问题但如果自定义一个结构体就必须自己提供哈希函数和相等判断函数否则编译直接报错。我在做一道“判断两个点是否重复”的题时踩过这个坑当时给结构体只重载了 operator结果 unordered_set 一直编译不过。后来换成 std::set 或者自己写哈希函数才解决。所以这里就涉及一个选择问题如果你需要有序集合就用 set如果需要快速查重优先用 unordered_set。但自己定义类型时set 只用重载 operatorunordered_set 却要同时配哈希和相等复杂度高得多。如果只是小规模数据直接用 set 反而更省心。5. 哈希表map计数和配对的核心工具5.1 map 的使用场景和常用操作今天的两道 map 题一道是“两数之和”另一道是“统计字符串中每个字符出现的次数”。map 的核心价值在于把“值”和“信息”关联起来比如把数组元素和它的下标关联、把字符和出现次数关联。最常用的三个操作是插入或更新mp[key] value判断是否存在mp.count(key)或mp.find(key) ! mp.end()遍历for (auto p : mp)两数之和的解法很经典用一个 unordered_map 保存“已经遍历过的数字 - 它的下标”每次处理新元素 target - num 时直接查 map 里有没有这个补数。因为只需要一次遍历时间复杂度 O(n)。vectorint twoSum(vectorint nums, int target) { unordered_mapint, int mp; for (int i 0; i nums.size(); i) { int complement target - nums[i]; if (mp.count(complement)) { return {mp[complement], i}; } mp[nums[i]] i; } return {}; }5.2 operator[] 的坑它真的会插入元素今天必须重点说一个坑因为我发现身边很多人在刷题时都被这个坑害过。map[key]这个操作如果 key 不存在它会默认创建一个值为 0或默认构造的条目再返回引用。也就是说当你想用if (mp[key])来判断某个 key 是否存在时这个操作本身就已经把 key 插进 map 里了。这会导致两个问题第一map 的 size 无端变大影响逻辑判断。第二在计数场景里如果直接写mp[key]而 key 原本不存在确实会得到 1这个行为是 C 的合法特性不算 bug但如果后续遍历时你不期望出现这个 key就会很困惑。正确做法是只读检查用 find 或 count需要新增或更新再用 operator[]。5.3 字符计数的经典写法今天那道统计字符的题我用的就是这个模板unordered_mapchar, int mp; for (char c : str) { mp[c]; } for (auto p : mp) { cout p.first : p.second endl; }这里 mp[c] 没有先判断是否存在是因为 operator[] 会自动插入初始化所以第一次累加就是从 0 变成 1。这个技巧被称为“默认值插入”在需要计数时非常好用但要注意只能用于不关心默认值干扰的场景。5.4 map 的遍历顺序和选择最后说一下 set 和 map 家族的选择。std::map 是有序的底层是红黑树插入查找都是 O(log n)。std::unordered_map 是无序的底层是哈希表插入查找平均 O(1)但最坏情况可能退化到 O(n)。刷题时如果题目不要求有序输出优先用 unordered_map如果要求按键排序输出就选 map。今天我统计完字符后把结果按字典序输出用的是 map因为有序遍历起来直接不用 sort。6. 常见问题与排查实录6.1 今日打卡问题速查表今天刷题过程中遇到和想到的常见问题我整理成了表格方便以后快速排查问题现象可能原因解决方案前缀和答案偏大或偏小查询时使用了 prefix[l] 而不是 prefix[l-1]确认下标从1开始统一用 prefix[r] - prefix[l-1]二维前缀和越界没有判断 x1-1 或 y1-1 是否小于0使用1-indexed存储并在循环条件中直接处理边界快慢指针死循环fast 或 fast-next 为空时仍继续访问 next循环条件写fast fast-nextset 编译报错自定义类型没有提供哈希函数改用 std::set 或为类型实现 std::hash 特化map 出现意外的 key用了 operator[] 做只读查询查询用 find/count确认 key 存在后再用 operator[]unordered_map 输出顺序杂乱本身无序题目可能要求有序输出改用 std::map或者先放入 vector 再排序6.2 给同样在刷题打卡的人几条建议连续刷了 20 天算法我的一个很明显的感觉是算法打卡最重要的不是每天刷多少题而是每天能不能把同一类技巧吃透。今天这 7 道题看起来很多但归纳下来其实就是五个点前缀和怎么预计算、二维的容斥原理怎么用、快慢指针怎么处理边界、set 怎么去重、map 怎么做计数。把知识点归类整理比盲目刷新题有用得多。我的习惯是每道题做完后把代码中容易出问题的三行左右记在笔记里不写完整题解只写“为什么这里会错”。比如今天的快慢指针判断我的笔记就是“fast-next 为空一定要先判断”。下次遇到同类题只需翻这一行。最后再分享一个小技巧打卡时把日期和星期标上比如今天的“day20 2026-03-12 周四”能让自己的节奏感更强。刷算法是长期战记录本身就是坚持的一部分。今天 7 道题全部 AC算是给第 20 天画了个圆满的句号。下一阶段我准备重点刷一下动态规划到时候再继续记录。