★ FEATURED ARTICLE 开门见山。这个月我把某个算法训练平台的基础算法课第三部分刷完了顺手整理了一份笔记。这部分内容集中在双指针、位运算、离散化和区间合并上四个看起来“小而美”的专题却是后面进阶算法里高频复用的基本功。先说结论这四个专题难度不大但非常讲究“技巧性”。很多初学者容易卡在“明明思路听懂了一写代码就错”的状态十有八九是没吃透这几类题目的固定套路和边界处理。这篇文章我尽量把每个专题的关键思路、典型代码、踩坑点都掰开讲清楚适合刚刷完排序和二分、正在往进阶走的同学参考。1. 双指针算法从暴力枚举到线性扫描的思维跃迁1.1 双指针到底在优化什么双指针算法听起来玄乎本质上就是把两重循环优化成一重循环。最经典的场景是一个数组里你需要枚举所有满足某种条件的子区间暴力写法是固定左端点i让右端点j从i扫到n时间复杂度O(n²)。双指针的优化思路是——让i和j都只往一个方向移动不会回退这样总移动次数是O(n)。为什么i和j都能不回退这才是理解双指针的关键。假设我们用i表示区间左端点j表示区间右端点当前区间[i, j]已经满足条件了。当i向右移动一步变成i区间变小了那么原来满足的条件在新区间里仍然可能满足而j不需要从i重新开始扫只需要基于原来的j继续扩展就行。这背后的逻辑是单调性——如果区间合法性和区间长度之间存在单调关系双指针就能生效。很多资料用“滑动窗口”来类比双指针其实这俩不完全是一回事。滑动窗口更强调“窗口”的形态左右边界都是浮动的而双指针还包括两个指针同向移动的“快慢指针”场景比如链表里找环。但在算法基础课这个阶段双指针基本就是用来处理数组/字符串子区间问题的按滑动窗口的思路去理解完全够用。1.2 最经典的模板最长连续不重复子序列这个题目是理解双指针的绝佳入口题目要求是给定一个长度为n的整数序列找出最长的不含重复数字的连续子序列长度。暴力思路很简单枚举起点i然后让终点j从i开始一直往右走用哈希表记录区间内每个数字出现的次数一旦发现重复数字就停更新答案。这个做法的复杂度是O(n²)n到10⁵就完蛋。双指针的做法长这样#include iostream using namespace std; const int N 100010; int a[N], cnt[N]; int main() { int n; cin n; for (int i 0; i n; i) cin a[i]; int res 0; for (int i 0, j 0; j n; j) { cnt[a[j]]; while (cnt[a[j]] 1) { cnt[a[i]]--; i; } res max(res, j - i 1); } cout res endl; return 0; }代码很短但每一行都有讲究。外层循环枚举的实际上是右端点j每次把a[j]加入窗口。如果加入后a[j]出现了两次说明窗口里有重复元素了那就移动左指针i把窗口左端的元素一个个从计数里去掉直到a[j]的计数恢复为1。内层while每执行一次i就右移一格。由于i在整个算法过程中只会向右移动不会回退总移动次数不超过n所以整体复杂度是O(n)。我最初学这段代码的时候有个疑惑为什么while里面只判断cnt[a[j]]是否大于1而不是检查整个窗口有没有重复答案在于——窗口在每一轮循环结束时一定是合法的加入新元素后唯一可能造成重复的只有这个新加进来的a[j]。所以只需要盯着它检查就够了。实际做题的时候数组开多大、cnt数组用不用memset清零、输入用scanf还是cin这些细节都能影响你是否在比赛中白白罚时。序列元素可能范围较大时更稳妥的做法是直接用unordered_map来计数但它的常数比普通数组大不少。如果题目没给值的范围可以考虑先离散化再用数组这个后面细说。1.3 双指针的扩展场景除了最长连续不重复子序列双指针还能处理很多看起来不太一样的问题。比如“数组元素的目标和”给定两个升序数组A和B再给定一个目标值x要求在A和B中各找一个数使得它们的和正好等于x。这类题的经典做法是i从A的头部开始j从B的尾部开始。如果A[i] B[j] x就让j左移如果小于x就让i右移刚好等于就输出答案。两个指针都只朝一个方向移动复杂度O(n m)。这里用到的单调性是A递增、B递减时两数之和关于i递增、关于j递减配合目标值就能像夹逼一样收敛到答案。另外还有一个高频变体是“判断子序列”。给定两个字符串判断较短的字符串是否是较长字符串的子序列。这本质也是双指针的经典应用——i指针指向短串j指针指向长串j不断向后移动一旦遇到与短串当前字符相同的字符i就前进一步。长串扫完时如果i走过的长度等于短串长度说明每个字符都能按顺序找到答案就是true。这类题目里有一个很实用的经验双指针的核心是找到那个“单调性的轴”。做题之前先问问自己左指针右移会导致什么变化右指针右移会导致什么变化两者的变化方向是否一致或者相反想清楚这个代码基本就不会写错方向。1.4 双指针常见错误清单双指针代码看似简单我见过身边不少人在这上面卡了很久总结下来就三类错误第一类是while循环条件写错。有些题需要外层枚举i、内层移动j有些题反过来外层枚举j、内层移动i。如果搞反了要么答案偏大漏掉了某些合法区间要么复杂度退化。我自己的习惯是先固定“扩展的那一端”再考虑“收缩的那一端”并不会每次都死记模板。第二类是忽略计数数组的恢复。比如上面最长不重复子序列的题当左指针i右移时必须把原来i位置的元素从cnt中减去。漏掉这一步窗口里的计数就会失真后续判断全部乱套。第三类是边界处理不当。比如子序列问题里j扫描完整个长串但i还没走完短串说明匹配失败再比如区间问题的双指针写法里内层while结束的条件是“i j”而不是“i j”因为当左指针越过右指针时区间已经空了。这些边界条件不处理干净代码很容易在线评测的极端数据上翻车。2. 位运算算法题里最不好直观理解的小技巧2.1 为什么算法题爱考位运算位运算在算法基础课里的戏份不算多但出现即高频——它主要用来解决一类关于二进制表示的问题最常见的就是统计一个数的二进制表示中有多少个1。这类问题的特点是用常规十进制思维很难想通一旦理解了二进制运算的底层机制代码又简洁得让人拍案叫绝。计算机里一切数据说到底都是二进制。位运算包括与、或|、异或^、取反~、左移、右移六种操作。算法题里最常用的其实是与运算配合右移操作来逐位提取以及一个特殊技巧叫lowbit运算——用来提取一个数二进制表示中最右侧的1。我做这类题最大的感受是不要试图用十进制数学直觉去推导要直接在纸上画出二进制位来模拟。有些规律光看代码很难体会画几遍二进制演变图就通透了。2.2 统计二进制中1的个数两种解法对比先看最常见的题目输入n个整数依次输出每个数的二进制表示中1的个数。n可以到10⁵甚至10⁶每个数在int范围内。解法一逐位右移判断int countOne(int x) { int res 0; while (x) { if (x 1) res; x 1; } return res; }这个思路非常直白x 1能取出x的最低位是1就计数加一然后x右移一位相当于丢掉最低位。循环直到x变成0为止。负数的右移是算术右移最高位补1所以这个写法在负数上会死循环——实际题目如果给的都是非负整数这个写法没问题但最好提前确认输入范围。解法二lowbit运算lowbit运算的定义是返回一个数的二进制表示中最低位的1所对应的数值。举个例子x 12时二进制是1100最低位的1在第2位从0开始计数对应数值就是4。lowbit(12) 4。计算lowbit有个著名公式x -x。为什么这个公式成立关键在于负数的二进制表示是原数的补码。x和-x进行按位与只有x最右侧的那个1位会保留下来其余高位都为0。不理解就去纸上画一下12和-12的二进制再对齐做与运算一眼就能看明白。统计1的个数就变成了int countOne(int x) { int res 0; while (x) { x - lowbit(x); res; } return res; }每次把x的最低位的1减去循环多少次就说明有多少个1。两种解法复杂度都是O(k)k二进制中1的个数。实际跑起来lowbit写法通常更快因为跳过了值为0的高位部分。2.3 lowbit运算的其他用途lowbit除了数1的个数还有一个重要应用场景——树状数组。树状数组里更新和查询都要用到i lowbit(i)和i - lowbit(i)这两个操作用来在逻辑的树形结构上跳跃。所以千万不要觉得位运算算1的个数只是个孤立的小技巧它其实是很多数据结构的基石。我在刷题过程中还发现lowbit能用来快速判断一个数是不是2的整数次幂如果x是正整数且x (x - 1) 0那x就是2的n次幂。这个等价于x的二进制表示里只有一个1。比循环判断高效得多而且一行代码就能写完。2.4 位运算题目的实操经验位运算的题代码写错通常不是逻辑错而是运算优先级出错。C里位运算的优先级低于比较运算容易写出if (x 1 0)这种实际上解析成x (1 0)的代码。处理办法很简单——尽量把位运算用括号包起来别嫌麻烦。另一个经验是涉及负数的位运算要格外小心。左移负数、右移负数、对负数取反行为在不同编译器/平台上可能符合预期也可能不符合。竞赛环境里如果输入范围限定在非负整数就放心用如果可能为负建议先确认题意。我自己的习惯是在纸上先演练两个用例一个值比较大的数比如2³¹ - 1一个边界数比如0或者1。0的特殊之处在于它的任何位运算结果都是0循环根本不会执行1则对应最低位为1的情况很多边界错误都藏在这样的两种用例里。3. 离散化让稀疏的大范围数据变得可处理3.1 什么时候需要离散化离散化这个词听起来高端实际上思路朴素得不能再朴素——把值域很大但个数很少的数据映射成从1开始的连续整数然后用数组代替哈希表来计数。很多题目里数据范围会这样设计n个操作每次操作涉及一个位置xx的范围可以达到10⁹但n本身只有10⁵。这时候你没法开一个长度10⁹的数组内存直接爆炸但如果你把所有出现过的x收集起来排序去重一共也就n个不同的值映射到1~mm≤n这m个连续下标上就能用普通数组来存储每个位置的值了。我最初学离散化时最大的困惑是为什么不直接用一个map或者unordered_map存原因在于两点。第一数组的随机访问比哈希表快得多常数小第二很多后续操作比如求前缀和、二分查找要求数据具有顺序性而离散化后的数组天然是保序的哈希表做不到。3.2 离散化的标准实现流程完整流程分三步收集-排序-去重然后是二分查找映射。第一步把所有可能出现的位置x存到一个vector里。第二步sort()排序然后用unique()和erase()去重。这两步配合使用是C的标准写法vectorint alls; // 把所有相关位置加入alls sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end());unique()会把重复元素移动到容器末尾返回新逻辑结尾的迭代器然后erase删掉后面的重复元素。这行代码应该背下来刷题常用。第三步实现一个映射函数把原始位置x映射到下标int find(int x) { int l 0, r alls.size() - 1; while (l r) { int mid l r 1; if (alls[mid] x) r mid; else l mid 1; } return l 1; // 从1开始方便前缀和 }这里返回l1而不是l是为了让映射后的下标从1开始。这样后面做前缀和的时候sum[i] sum[i-1] a[i]不需要单独处理0号下标能省很多边界判断的麻烦。这是一个很小的经验但能让你写代码时少踩不少坑。3.3 典型例题区间和有一道经典题叫区间和描述是这样的坐标轴上有一个数轴n次操作在某个位置x加上一个数c然后m次询问每次问[l, r]区间内所有数的和。x、l、r的范围可以到10⁹但n和m之和不超过10⁵。做法就是在读入所有操作时把x、l、r都收集到alls里排序去重后用离散化后的下标存储每个位置的值然后求前缀和数组再对每次询问在alls里二分定位到离散化后的下标用前缀和相减得出区间和。完整代码如下#include iostream #include vector #include algorithm using namespace std; typedef pairint, int PII; const int N 300010; int a[N], s[N]; vectorint alls; vectorPII add, query; int find(int x) { int l 0, r alls.size() - 1; while (l r) { int mid l r 1; if (alls[mid] x) r mid; else l mid 1; } return l 1; } int main() { int n, m; cin n m; for (int i 0; i n; i) { int x, c; cin x c; add.push_back({x, c}); alls.push_back(x); } for (int i 0; i m; i) { int l, r; cin l r; query.push_back({l, r}); alls.push_back(l); alls.push_back(r); } sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); for (auto item : add) { int idx find(item.first); a[idx] item.second; } for (int i 1; i alls.size(); i) s[i] s[i - 1] a[i]; for (auto item : query) { int l find(item.first), r find(item.second); cout s[r] - s[l - 1] endl; } return 0; }这个例子信息量很大它同时用到了离散化、二分查找和前缀和是一个综合性的应用场景。如果把这段代码吃透不仅离散化会了二分的边界处理和前缀和的思想也能得到巩固。3.4 离散化避坑要点第一alls数组里必须把查询的l和r也加入。很多人一开始只加入修改操作的位置x结果查询时在alls里找不到l和r对应的下标代码直接越界。别问我是怎么知道的。第二find函数的前提是x一定存在于alls中。因为所有可能出现的坐标在收集阶段都加入了alls所以查找一定能找到。如果你自定义的数据没有提前收集就调用find二分结果就不确定。第三unique和erase的搭配。有些C版本里unique返回的迭代器指向去重后的最后一个元素的下一个位置如果忘记erase后续用alls.size()取长度时会把重复元素也算进去导致a数组分配空间不够或者find出现逻辑错误。第四下标从1开始的收益。前面提到了从1开始做前缀和可以避免对下标0的特殊处理。如果你第一次写的时候下标从0开始你会发现后面处理前缀和时要额外判断l 0的情况烦得很。从我个人的体验来说这个从1开始的小习惯值得刻意养成。4. 区间合并贪心思想的第一次真正落地4.1 问题定义与解题思路区间合并是基础算法课里一个承上启下的内容。题目描述很简单给定n个区间把有重叠包括端点相接的区间合并成一个区间最后输出合并后的区间个数和每个区间的起止位置。暴力做法是先对每个区间遍历其他区间判断是否重叠时间复杂度O(n²)更麻烦的是区间合并的结果还可能级联合并后的新区间又和其他区间重叠。所以这类题的标准解法是贪心先把所有区间按照左端点从小到大排序然后依次扫描维护一个当前合并区间的右端点。贪心的正确性在于排序后左端点小的区间一定先被处理。当前扫描到的区间是否要和维护中的区间合并完全取决于它的左端点是否不超过当前区间的右端点——如果不超过则重叠需要把右端点更新为两者中较大的值如果超过则维护中的区间已经无法与后续任何区间合并可以输出并重新开始维护新的区间。4.2 代码实现与细节#include iostream #include vector #include algorithm using namespace std; typedef pairint, int PII; void merge(vectorPII segs) { vectorPII res; sort(segs.begin(), segs.end()); int st -2e9, ed -2e9; for (auto seg : segs) { if (ed seg.first) { if (st ! -2e9) res.push_back({st, ed}); st seg.first, ed seg.second; } else { ed max(ed, seg.second); } } if (st ! -2e9) res.push_back({st, ed}); segs res; } int main() { int n; cin n; vectorPII segs; for (int i 0; i n; i) { int l, r; cin l r; segs.push_back({l, r}); } merge(segs); cout segs.size() endl; return 0; }这里的st和ed初始值设置成-2e9是因为区间坐标可能为负用极小值初始化使得第一次扫描时不会误判为“不重叠”。最后扫描结束后还要把最后一个未输出的合并区间push进结果数组这地方漏掉的话答案会少一个区间。4.3 端点重合的处理策略判断两个区间是否重叠标准写法是判断当前区间的左端点是否大于维护区间的右端点。也就是ed seg.first时不重叠否则重叠。注意这里用的是严格小于说明当ed seg.first时前一个区间的右端点和后一个区间的左端点重合我们仍然认为它们重叠并合并。这个细节在不同题目里有不同要求。有些题目明确说区间端点相接触不算合并那判断条件就要变成ed seg.first。我建议每次做题先读清楚题目里对“重叠”的定义不要想当然地套模板。4.4 区间合并的变体与应用区间合并看起来教学意义大于实用意义但它实际上是很多复杂区间算法的基石。比如扫描线算法求矩形面积并初始步骤就是把所有矩形的竖边按x坐标排序然后用类似区间合并的方式维护当前覆盖区间的y方向长度。再比如求最多能保留多少个互不重叠的区间区间选点问题也是先排序区间再用贪心策略。所以在这个阶段花一点时间把区间合并彻底吃透是值得的。我自己的感受是算法学习到后面会发现很多高级内容都能拆解成基础算法的组合区间合并 线段树、区间合并 差分、区间合并 扫描线等都是很常见的组合拳。经验提示排序pair默认先按第一关键字升序再按第二关键字升序。区间合并只依赖左端点单调递增右端点顺序无所谓所以直接对vectorPII排序即可。但如果你写的是自定义结构体记得在sort时传入cmp函数。4.5 写区间合并时的三个易错点我先说我自己踩过的一个坑只更新右端点不取最大值。如果不取max当新区间完全被当前合并区间包含时合并后的右端点反而变小了后续判断全部错乱。所以合并时的右端点更新一定是ed max(ed, seg.second)不是ed seg.second。第二个坑是忘记最后一段的入库。循环结束时维护的区间已经无法与后续区间合并但还没有push进res需要在循环外单独处理一次。写代码理流程的时候拿两个用例模拟一遍就能发现。第三个坑是初始值设置不当。如果区间坐标全为正数初始值设成-1可能没问题但坐标可以为负时就必须设成一个足够小的数。还有一个细节是初始值要能保证“第一次扫描时不产生误判”一般用-2e9或INT_MIN都能达到目的但有些同学习惯用0就会出问题——题目给的最小坐标是-10时第一次扫描就全乱套了。5. 从笔记到能力的两个关键习惯5.1 用自己的语言整理模板而不是抄模板这一部分内容我写笔记的时候最大的体会是模板要自己推导一遍再写进笔记。直接抄老师或者题解里的模板当时看懂了过两天就忘记了。但如果能自己把双指针的移动过程、位运算lowbit的推导、离散化为什么下标从1开始等问题重新表述一遍就会真正内化成自己的东西。我在笔记里给每个算法都配了一个“为什么这样写”的段落用大白话解释每一步的逻辑。比如双指针模板里为什么要cnt[a[j]]在先、while判断在后再比如离散化的find函数为什么用二分而不是直接用lower_bound。就是这些“为什么”在考试和比赛中帮助我快速还原代码而不是死记硬背。5.2 刷题时主动给题目归类基础算法这个阶段题目类型非常鲜明做题时不用追求题量但每道题要想清楚它考的是哪个专题的哪个变体。我在刷题时会记录一个表格写上题目编号、核心算法、特殊之处、犯了什么错、怎么改对的。这样到后面的图论、动态规划阶段遇到新的题目能迅速联想到“这题可以拆成区间合并贪心”“这题就是双指针排序”等组合解题速度快很多。6. 写在最后基础不牢地动山摇这一篇笔记覆盖的双指针、位运算、离散化和区间合并单个拿出来看难度都不高组合起来能覆盖的题目范围却非常惊人。我个人最深的体会是刷题快慢不取决于你背了多少模板而取决于你对每个基础专题的理解有没有到位。双指针的单调性、位运算的二进制直觉、离散化的保序映射、区间合并的贪心证明每一个都值得多花半小时慢慢消化。如果你现在刷这些题感觉有点吃力不用慌这是非常正常的阶段。我当初也是把最长连续不重复子序列那道题写了三遍才彻底搞懂。多写几遍多模拟几个极端用例很快就能找到感觉。下一篇笔记我会继续整理基础算法里剩余的内容包括高精度运算和前缀和差分。到时候见。
阅读完成 · 觉得有帮助？
