企业官网建设流程全解析

双指针、位运算、离散化、区间合并，这六个算法如果是第一次接触，会觉得“不过如此”，但题目一变式就手足无措。这篇笔记把我在算法基础课第三部分学到的东西重新捋了一遍，重点不是贴模板，而是把每个算法“为什么这么写”“坑在哪里”讲清楚。无论你是刚学完排序二分的新手，还是准备秋招在刷基础题的选手，这篇都能帮你省下不少自己踩坑的时间。

1. 第三讲在整套课程里的位置：为什么单独拆出这五个算法

基础算法作为整套课程的开篇，前两讲覆盖了排序（快排、归并）、二分（整数二分、浮点二分）、高精度、前缀和与差分。到了第三讲，内容突然变得“工具化”了：双指针、位运算、离散化、区间合并，外加一个排序相关的扩展。

1.1 从“读写代码”到“优化思路”的转折点

前两讲的核心是建立“能跑”的代码能力，而第三讲开始，重点转向“怎么跑得更快”。双指针涉及的复杂度优化，是很多题目从 O(N²) 降到 O(N) 的突破口；位运算则是后续树状数组、状态压缩DP必备的底层思维；离散化和区间合并属于“数据预处理”的范畴，看起来简单，但边界条件和实现细节极其容易写错。

这部分学完，你再回头做前缀和、差分相关的题，会有一种“原来还能这么组合”的感觉。比如区间合并和差分结合，可以解决很多区间覆盖计数的问题；离散化和前缀和结合，则是经典的“区间和查询”套路。

1.2 前置知识要求：只需要稳扎稳打的前两讲

第三讲对基础的要求其实不高，但前两讲里有些东西必须吃透，否则会很吃力：

• 排序必须理解“稳定性”这个概念，虽然快排不稳定，但归并稳定，离散化用不到，可后面区间合并的排序策略会用到。
• 二分的整数边界处理要熟练，因为离散化后查找索引用的就是整数二分。
• 前缀和的含义要清晰，区间合并虽然不直接用，但很多变式题会混着考。

我在学习时的一个体会是：第三讲的每个算法单独拿出来都简单，但它们互相组合之后，难度直接翻倍。这也是为什么需要在基础阶段就把它们各自写熟。

2. 双指针：从暴力到 O(N) 的压缩套路

双指针的核心思想一句话就能说完：维护两个指针（下标），按照某种单调的规则移动，把两重循环优化成一重。但什么时候用、怎么写不会死循环，才是真正的考点。

2.1 双指针的本质：把两重循环压缩成一重

先看一个最经典的场景：给定一个有序数组和一个目标值，找出两个数使得它们的和等于目标值。暴力做法是枚举 i 和 j，双重循环 O(N²)。

双指针的做法是：

• 一个指针 i 指向开头，一个指针 j 指向结尾。
• 如果 a[i] + a[j] > target，说明和太大了，j 左移。
• 如果 a[i] + a[j] < target，说明和太小了，i 右移。
• 如果相等，就找到了答案。

为什么这样不会漏解？假设当前 i 在某个位置，j 在结尾，此时和大于 target，说明 a[i] 与任何更靠右的元素相加都更大（因为数组有序），所以可以把 a[i] 排除，i 必须右移。同理，和小于 target 时，a[j] 与任何更靠左的元素相加都更小，所以 j 必须左移。每一步都排除了至少一个元素的可能组合，最终不会错过正确答案。

这个思想推广开来，就是“单调性”：指针的移动方向是确定的，不会来回反复。

2.2 三个高频应用场景与对应模板

第一种是最长连续不重复子序列。典型题目是“给定一个序列，找到最长的一段，使得这段内没有重复元素”。写法是用一个哈希表（或者数组计数）维护当前窗口内元素出现次数，右指针扩展时计数加一，一旦出现重复，左指针右移直到计数恢复为 1。

伪代码逻辑如下：

int l = 0, r = 0, ans = 0; unordered_map<int, int> cnt; while (r < n) { cnt[a[r]]++; while (cnt[a[r]] > 1) { cnt[a[l]]--; l++; } ans = max(ans, r - l + 1); r++; }

这里的核心是：右指针每次固定向前走一步，左指针虽然也在移动，但只会向右移动。总移动次数 O(N)。

第二种是归并排序中的归并过程。两个有序数组合并成一个有序数组，两个指针分别指向两个数组，比较当前元素大小，小的放入结果并移动对应指针。这个逻辑在链表题里也经常用到，比如合并两个有序链表，只是链表要小心空指针。

第三种是快慢指针，典型场景是检测链表是否有环。快指针每次走两步，慢指针每次走一步，如果有环，两者必然相遇。

我在实际刷题中发现，双指针最容易被忽略的点是窗口内状态的维护。比如“最长不重复子序列”里，右指针扩展时要及时更新状态，左指针收缩时也要同步更新，漏一个就出错。

2.3 双指针的复杂度推导与为什么能AC

很多人只知道双指针快，但不知道为什么。我自己的理解是：双指针之所以从 O(N²) 降到 O(N)，本质是消除了一维的无效枚举。

暴力做两数之和时，外层枚举每个 i，内层枚举每个 j，相当于枚举了所有数对，N² 个。双指针做同样的任务时，i 和 j 的移动总量加起来不超过 N 次（每轮至少移动一个指针，最终 i 和 j 相遇），所以总操作数 O(N)。

我之前给某群友讲这个时打过比方：暴力做法是全班两两握手，双指针做法是所有人排成一排，一个人从左边走，一个人从右边走，需要相遇时就是答案。听起来像是“只做了 N 次握手”，其实是因为每次移动都排除了大量不必要的组合。

3. 位运算：从 lowbit 到状态压缩的底层思维

位运算这部分内容不多，但极其重要。我在学第一遍时觉得“不就是 &、|、^、<<、>> 吗，有什么好讲的”，后来才发现，位运算是很多高级数据结构和 DP 优化的基石。

3.1 lowbit 操作：树状数组和二进制拆分的钥匙

lowbit(x) 返回 x 的二进制表示中最低位的 1 所代表的值。比如 x=12（二进制 1100），lowbit(x)=4（二进制 100）。

实现方式极其简单：

int lowbit(int x) { return x & -x; }

为什么 x & -x 能得到最低位的 1？因为负数的二进制表示是原码取反加一。取反后，最低位的 1 变成 0，后面的 0 变成 1，加一后最低位那个 1 又恢复成 1，而更高位恰好和原数互补，& 运算后只有最低位的 1 保留了下来。

lowbit 最常见的用途是树状数组的 update 和 query 操作。它在二进制下不断剥离最低位的 1，相当于沿着树状数组的“覆盖链”向上或向下跳。当时我学树状数组时，就是靠把 lowbit 的手动模拟跑通后才真正理解的。

3.2 二进制枚举：把集合的交并补换成位运算

另一个高频场景是枚举子集。如果要枚举一个大小为 N 的集合的所有子集，可以用 0 到 (1<<N) - 1 的每个整数表示一个子集，第 i 位为 1 表示选取第 i 个元素。

模板如下：

for (int mask = 0; mask < (1 << n); mask++) { for (int i = 0; i < n; i++) { if (mask >> i & 1) { // 第 i 个元素在子集中 } } }

这里判断第 i 位是否为 1，写法是mask >> i & 1，优先级要特别注意，移位优先级高于按位与，但为了防止歧义，建议写成(mask >> i) & 1或者mask & (1 << i)。

我最早写的时候习惯用mask & (1 << i)，后来看别人的代码发现很多人用位移写法，其实就是前面加了括号，各位别看漏了。

3.3 位运算的几个坑位：优先级、符号位和溢出

位运算最容易翻车的地方是优先级。在 C++ 中，按位与&的优先级低于等于==，这意味着if (x & 1 == 0)会被解析成if (x & (1 == 0))，直接变成判断 x 是否为 0。这种情况必须加括号。

另一个坑是右移负数的行为是“实现定义”的，虽然大多数平台是算术右移（补符号位），但写竞赛代码时尽量只对非负数做右移，避免意外结果。

溢出问题也很常见。1 << n当 n 很大时，1 是 int 型，可能溢出。稳妥写法是1LL << n或者(1u << n)。

4. 离散化：大值域稀疏数据的压缩方法

离散化这名字听起来很高级，实际上做的事情很简单：把稀疏分布的大整数坐标，映射到连续的小整数区间上，从而可以用数组下标来索引。它本身不复杂，但和树状数组、前缀和、线段树结合时，就变成了一道题的关键预处理。

4.1 什么时候必须离散化

当题目里的数据范围极大（比如坐标从 -1e9 到 1e9），但实际出现的坐标数量很少（比如只有 1e5 个），直接开数组不可行，这时就需要离散化。

一个典型例子是“区间和”的变体题：在数轴上某些点加值，然后查询若干区间和。坐标的范围超大，但实际修改和查询涉及的坐标数量有限，把所有相关坐标收集起来，排序去重，映射到 0..m-1 的连续下标上，之后所有操作都针对这个映射后的数组进行。

4.2 手工实现的三板斧：排序、去重、二分查找

离散化手工实现就三步：

1. 把所有可能用到的坐标放入一个 vector。
2. sort + unique 去重。
3. 通过二分（lower_bound）把原坐标映射为数组下标。

代码模板：

vector<int> alls; // 把所有涉及的坐标 push 进 alls sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); int find(int x) { return lower_bound(alls.begin(), alls.end(), x) - alls.begin(); }

这里有个细节：unique返回的是去重后新逻辑末尾的迭代器，erase之后，alls里就是排序去重后的坐标序列。find返回的是下标，从 0 开始。

实际操作中我遇到最多的问题是忘记把所有会用到的坐标都收集进 alls。比如修改操作涉及的坐标收集了，但查询操作中用到的坐标没收集，后续二分就找不到，直接数组越界或者结果错误。

4.3 离线处理思想与坐标还原

离散化天然配合“离线查询”：先把所有操作读入，记录下来，再统一处理。

坐标还原则是在输出答案时用到的。离散化时，我们建立的是“原坐标 -> 映射下标”的映射。如果某个答案是“第几个坐标位置上的值”，你需要根据下标找原坐标，可以维护一个反向数组，或者直接用 alls[index] 取回原坐标。

我自己的建议是：在写离散化前先想清楚，题目最终要输出的是值还是坐标。如果是坐标，务必保留 alls 数组本身，不要覆盖掉，否则输出时恢复不了。

5. 区间合并：一套固定模板吃透区间交叠问题

区间合并是这五个算法里“最模板化”的一个，但它出现在很多题目的前置步骤里，比如经典的“合并区间”“会议室占用”“最少箭射气球”等。核心都是一样的逻辑。

5.1 区间合并的核心不变量：排序后相邻区间的三种关系

给定若干区间 [l, r]，合并有交集的区间。思路是先把区间按左端点排序，然后依次处理。

排序后，对于当前区间 cur 和下一个区间 next，只有三种情况：

• next.l > cur.r：完全不相交，cur 直接结束，答案加入 cur，cur 更新为 next。
• next.l <= cur.r 且 next.r > cur.r：有交集，合并后的右端点更新为 next.r。
• next.r <= cur.r：next 完全被 cur 包含，什么都不做，cur 不变。

合并的核心不变量是：处理完前 i 个区间后，当前合并区间的右端点是已经处理过的区间中能到达的最右位置。

这一句话就解释了为什么排序后只需要看下一个区间的左端点和当前右端点的关系。

5.2 合并模板与边界条件处理

代码模板如下：

vector<pair<int, int>> merge(vector<pair<int, int>>& segs) { sort(segs.begin(), segs.end()); vector<pair<int, int>> res; int st = -2e9, ed = -2e9; for (auto seg : segs) { if (seg.first > ed) { 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}); return res; }

这里的st和ed初始化为一个极小值，用来标志“当前还没有区间”。循环结束后还要把最后一个区间 push 进去，这是个容易漏掉的地方。

边界条件有几个要小心：

• 如果输入区间集合为空，st保持初始值，最后那个if判断避免把无效区间加进去。
• 如果区间左端点相同，按右端点排序，但由于我们用的是 pair 默认排序（先按 first 再按 second），左端点相同时右端点较小的会排前面，这对合并逻辑没有影响，因为右端点取 max。
• 如果题目要求的是“合并后区间的数量”，只需要统计 res.size() 即可。

5.3 区间合并的常见变式：求覆盖长度和覆盖次数

区间合并模板不仅用于合并，还能扩展。比如求所有合并后区间的总长度，可以在每次确定一个新区间时累加ed - st。

再比如区间覆盖次数统计，需要离散化加差分：对每个区间 [l, r]，在差分数组的 l 位置加一，r+1 位置减一，然后前缀和还原。这个思路经常和离散化搭配使用，因为坐标范围可能很大。

我刷题时最大的体会是，区间合并的模板本身只有十几行，但难点在于识别它。有的题表面看是“安排最少会议室”，其实第一步就是区间合并的变形。

6. 常见问题排查与避坑实录

第三讲的代码量不大，但坑不少。我把自己和周围人踩过的坑整理了出来，写成一张速查表。

6.1 双指针死循环和漏更新状态

双指针最容易犯的错是把while (cnt[a[r]] > 1)里的右指针写成左指针，看起来差不多，运行起来直接死循环。写完之后先拿几个手算例子跑一遍，别急着提交。

6.2 位运算优先级和溢出问题

位运算的报错往往比较隐蔽，程序不崩，但答案全错。常见情况：

• mask & (1 << i) == 0被解析成mask & ((1 << i) == 0)，结果恒为 0。
• 1 << 31直接溢出成负数，导致枚举的子集少了一半。

针对第一类，我用一个笨办法保证不出错：位运算表达式一律加括号，不要依赖优先级。针对第二类，凡是位移到接近 int 上限的，直接用long long或者无符号类型。

6.3 离散化丢坐标和重复元素处理

我第一次写离散化时忘记把查询区间的端点加入 alls，结果每次查询都是 0，调了半天。你如果也遇到“输入没问题但结果全错”的情况，先检查收集坐标这一步。

6.4 区间合并的端点相等问题

区间合并时，[1, 2]和[2, 3]要不要合并？题目如果明确说“端点相交就算重叠”，那就要合并，判断条件用next.l <= cur.r。题目如果说“端点不影响”，就不能合并，判断条件用next.l < cur.r。

这其实和“图论里边的端点是否算相交”是一个思路，取决于语义。我的习惯是在写之前先读题确认边界定义，不然一旦写反，答案可能差一。

另外注意排序时按左端点排序，如果左端点相同，右端点从小到大，这样后续合并取 max 时逻辑更清晰。

7. 个人学习经验：怎么把第三讲真正吃透

说了这么多，最后分享几个我在实际学习中的习惯。

第一个习惯是：每个算法学完之后，不看模板，自己在空白编辑器里写一遍。不是背，是默写。写错的地方就是你还没理解透的地方。第三讲的五个算法都很短，默写一遍花不了十分钟，但收益很大。

第二个习惯是：把每个算法的“适用条件”写下来贴在显眼的地方。比如双指针常用于有序数组、链表回文检测、滑动窗口；位运算常用于集合表示、状态压缩、快速判断奇偶；离散化常用于坐标范围大的稀疏数据；区间合并常用于交叠问题。有了这张表，刷题时看到题干就能快速判断该往哪个方向想。

第三个习惯是：刻意做组合题。第三讲单独学完只是第一步，真正的高手是把它们组合起来用。我自己练过一道题，需要坐标离散化、区间合并、差分前缀和三个知识点串在一起，做完那题我才意识到基础算法从来不是孤立的。

这段时间的学习让我最大的感受是：基础算法很简单，但“什么场景用什么算法”这个意识需要在题目里反复摩擦才能建立。如果你也在学这一讲，别急着往后赶，把这一部分吃透，后面学数据结构会顺畅很多。