企业官网建设流程全解析

从零开始刷算法题的人，大多都有过这种体验：今天看懂了快排，明天见到堆排又是一张新面孔，后天遇到滑动窗口直接懵圈。其实问题不在于算法本身有多难，而在于你没有一个清晰的“学习地图”。我的“算法DAY4”打卡，选在基础数据结构过完一轮之后，正好是把排序、双指针这些高频考点彻底揉碎了吃透的节点。这篇笔记不是什么天才速成法，就是一个普通程序员每天雷打不动两小时刷题的真实记录，今天重点啃两块硬骨头：一类是归并排序和堆排序背后的“分治+堆结构”思想，另一类是双指针与滑动窗口这套“线性扫描”打法。无论你是准备面试冲刺、校招笔试，还是工作中想写出更优雅的代码，这几板斧都值得花时间练扎实。

我先把DAY4的整体学习思路摆出来，后面每个专题都会给完整代码、复杂度推导、易错点和排查经验，方便你直接照着练。

1.1 为什么把排序和双指针放在同一天学

排序算法不是孤立存在的知识点，它是后续很多算法的基础设施。比如二分查找依赖有序数组，求逆序对依赖归并排序的合并过程，TopK问题直接靠堆排序的堆化操作。所以DAY4把排序放在前面，等于先搭好脚手架，后面学二分、学贪心、学树状数组的时候，你会觉得这些高阶算法凭空简单了三分之一。

双指针和滑动窗口放在排序后面学，是因为它们俩经常配合使用。最典型的就是“在有序数组里找两数之和”——先排序，然后左右指针往中间逼近。如果一道题既考排序又考双指针，你两样都熟，那基本就是直接秒杀。我见过太多人只刷分类题，刷排序不练指针，结果面试官换了一道“先排序再两边夹”的变种题就卡住。这就是典型的知识点没有串成线。

1.2 DAY4需要具备的前置基础

如果你是完全零基础，我不建议你直接跳到DAY4，起码得先过一遍数组、链表、递归和基本复杂度分析。这里的“基本复杂度”不是说你要背下所有大O表格，而是至少要能算出简单循环的复杂度，比如双层for循环是O(n²)，二分是O(logn)，这个必须口算。

另外我默认你已经会写冒泡排序和选择排序。因为DAY4里我讲归并和堆排的时候，会和冒泡做对比，方便你理解为什么有些排序是O(n log n)，有些是O(n²)。如果你连冒泡都手写不利索，建议先回去花两天把数组遍历和交换元素练熟，然后再回来打卡今天的题目。

2. 归并排序：分治思想的标准样板

2.1 归并排序的完整实现与复杂度推导

归并排序是我见过的“最符合人类直觉”的排序算法，前提是你先理解清楚它的分治过程。核心思路一句话：把数组从中间切开，左边排好序，右边排好序，然后把两个有序数组合并成一个。递归的子问题也是同样的逻辑，直到数组只剩一个元素——一个元素天然有序，递归天然终止。

void mergeSort(vector<int>& nums, int left, int right) { if (left >= right) return; int mid = left + (right - left) / 2; mergeSort(nums, left, mid); mergeSort(nums, mid + 1, right); merge(nums, left, mid, right); } void merge(vector<int>& nums, int left, int mid, int right) { vector<int> temp(right - left + 1); int i = left, j = mid + 1, k = 0; while (i <= mid && j <= right) { if (nums[i] <= nums[j]) temp[k++] = nums[i++]; else temp[k++] = nums[j++]; } while (i <= mid) temp[k++] = nums[i++]; while (j <= right) temp[k++] = nums[j++]; for (int p = 0; p < temp.size(); ++p) { nums[left + p] = temp[p]; } }

这里有几个我第一次写的时候没注意到的点。第一，mid的计算要用left + (right - left) / 2，而不是(left + right) / 2，虽然大多数情况下结果一样，但当 left 和 right 都是很大的正整数时，后者可能溢出。这个习惯要从第一天就养成，后面写二分查找写线段树都用得到。第二，合并的过程像什么？想象你手上有两副已经按从小到大摆好的扑克牌，你要把两幅牌合成一副有序的，就是每次从两堆牌顶取更小的那张放到结果里。这就是“归并”这个词的由来。

复杂度推导其实很简单。每次递归把问题规模减半，递归深度是 log n，每一层合并的总工作量是 n（所有元素在每一层都会被扫描一次），所以总时间复杂度是 O(n log n)。空间复杂度是 O(n)，因为每次合并都要开一个临时数组，虽然每一层递归结束后临时数组会被释放，但递归下来最多同时存在的临时空间总量是 O(n)，这个是面试官常问的点，别答错了。

2.2 一个经典实战：用归并排序求逆序对

逆序对问题，一句话定义是：数组中如果 i 小于 j，但 nums[i] 大于 nums[j]，这就是一对逆序。比如 [2, 4, 1, 3] 里，(2,1)、(4,1)、(4,3) 都是逆序对，一共3对。你当然可以两个for循环暴力枚举，但一旦数组长度到十万级别，O(n²) 直接爆炸。

归并排序求逆序对是“算法DAY4”里我强烈建议你手写一遍的题，因为它在归并排序基础上改动极小，但思想跨度很大。核心逻辑藏在合并这段：当nums[i] > nums[j]时，说明左半数组从 i 到 mid 的所有元素，全都比当前右半数组的 nums[j] 大，因为左右两半内部都已经有序了。所以此时逆序对的数量直接就是mid - i + 1。

long long countReversePairs(vector<int>& nums, int left, int right) { if (left >= right) return 0; int mid = left + (right - left) / 2; long long res = 0; res += countReversePairs(nums, left, mid); res += countReversePairs(nums, mid + 1, right); int i = left, j = mid + 1; vector<int> temp; while (i <= mid && j <= right) { if (nums[i] <= nums[j]) { temp.push_back(nums[i++]); } else { res += mid - i + 1; temp.push_back(nums[j++]); } } while (i <= mid) temp.push_back(nums[i++]); while (j <= right) temp.push_back(nums[j++]); for (int p = 0; p < temp.size(); ++p) nums[left + p] = temp[p]; return res; }

我第一次做这题的时候，贪心想直接在原冒泡排序里加一个计数器，结果数据一大就超时，后来才想明白：能统计逆序对的前提是“左右两半内部已经有序”，而你只能在归并的过程中拿到这个信息。这就是为什么归并排序能“顺手”统计逆序对，而冒泡排序做不到。

2.3 归并排序的边界条件与易错点

归并排序的代码看着短，但容易写错的地方其实不少。第一个经典错误是合并时把左右两半的边界弄混。你记住一句话：左半区间的范围永远是 [left, mid]，右半区间永远是 [mid+1, right]。如果你在 while 循环里写成了i <= right或者j <= mid，最后结果就是数组被随机打乱，数据量小的时候可能还侥幸对，数据量一大必错。

第二个易错点是临时数组的回收和拷贝。很多人图省事，每次 merge 都重新 new 一个数组，但忘记把合并后的结果拷回原数组，导致上层递归拿到的还是没排序的数组。调试的时候特别恶心，因为小数组有时候碰巧对。我的习惯是合并完成后马上写一个循环把临时数组拷回，然后再 return。

第三个坑是递归终止条件。left >= right表示区间里只有一个元素或者空，这时候必须直接返回。有人喜欢写left == right，其实也可以，但>=更稳妥，因为有些边界调用会传入非法区间。

3. 堆排序与优先队列：数组模拟二叉树的精髓

3.1 堆的底层逻辑与堆化操作

堆，本质上是一棵完全二叉树，但它不是用链表节点存的，而是用数组存的。数组下标 i 的左孩子是 2i+1，右孩子是 2i+2，父节点是 (i-1)/2。这个映射关系是堆排序的根基，也是优先队列能高效实现的根基。

大顶堆的定义是每个父节点都大于等于它的两个子节点，小顶堆恰好相反。堆的核心操作有两个：一个是下沉（sift down），把某个节点不断往下和更大的子节点交换，直到堆结构恢复；另一个是上浮（sift up），把末尾节点不断往上和父节点交换。堆排序只用到下沉，而优先队列的入队操作用上浮。

3.2 手写堆排序的完整代码

堆排序的思路分两步。第一步，把无序数组构建成大顶堆；第二步，把堆顶元素（最大值）和当前数组的最后一个元素交换，然后把堆的大小减一，对新的堆顶做下沉操作。重复这个过程，直到堆只剩一个元素。

void siftDown(vector<int>& nums, int i, int heapSize) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < heapSize && nums[left] > nums[largest]) largest = left; if (right < heapSize && nums[right] > nums[largest]) largest = right; if (largest != i) { swap(nums[i], nums[largest]); siftDown(nums, largest, heapSize); } } void heapSort(vector<int>& nums) { int n = nums.size(); for (int i = n / 2 - 1; i >= 0; --i) { siftDown(nums, i, n); } for (int i = n - 1; i > 0; --i) { swap(nums[0], nums[i]); siftDown(nums, 0, i); } }

建堆为什么从n/2 - 1开始往下遍历？因为这些节点是最后一批有子节点的父节点，再往下就是叶子节点，叶子节点不需要下沉。从这里开始从下往上调整，能保证每个子树都是堆。我第一次写的时候直接从n-1开始遍历所有节点，也“看起来对”，但那是多余的，而且如果数据量大会慢不少。

堆排序的时间复杂度是 O(n log n)，关键是建堆过程其实是 O(n)，为什么建堆是 O(n)？我在DAY4里花了很长时间才真正理解。因为从 n/2 到 0 一共有 n/2 个节点，越靠近根节点的节点数量越少，而且每个节点下沉的代价和它的高度相关，这些代价加总不是 n log n，而是约等于 n。面试如果深挖复杂度分析，这个点经常被问到，值得提前准备一下。

3.3 堆排序、快排、归并排序怎么选

很多人学完堆排序会问：既然堆排序最坏也是 O(n log n)，比快排的 O(n²) 好，那为什么实际工程里快排还是主流？这个问题问到点子上了。堆排序虽然复杂度稳定，但它对CPU缓存不友好——它访问数组是跳跃式的（顺着父子指针跳来跳去），而快排是顺序扫描。现代CPU读缓存是连续读快，所以快排实际跑起来往往比堆排快。

归并排序好在哪里？稳定且适合外部排序——当数据量大到内存装不下，你只能一部分一部分读进来排序再写出去，归并的“合并”阶段天然适合磁盘上的有序分段文件合并。但是归并需要 O(n) 额外空间，在内存敏感的场景就成了短板。

我个人的实操结论是：普通数组排序直接用 C++ 的sort()或者 Python 的sorted()，它们底层是内省排序（快排+插排混合），已经优化得很强；但面试会问原理，所以手写快排、归并、堆排都得会。优先队列则是堆的“实战形态”，求 TopK、合并K个有序链表、Dijkstra 最短路都要用它。

4. 双指针与滑动窗口：把暴力扫描降维成线性

4.1 快慢指针：链表环形检测的代表

双指针第一大类是快慢指针，最经典的题是判断链表是否有环。一个指针每次走一步，一个指针每次走两步，如果有环，两个指针必然相遇。这个结论可以用“跑步套圈”来理解——在环形跑道上，速度快的人迟早追上速度慢的人。

bool hasCycle(ListNode* head) { if (!head || !head->next) return false; ListNode* slow = head; ListNode* fast = head->next; while (slow != fast) { if (!fast || !fast->next) return false; slow = slow->next; fast = fast->next->next; } return true; }

快慢指针还有一个进阶应用：找链表中点。快指针到终点时，慢指针正好到中点，这个技巧在处理链表排序（比如对链表做归并排序找中点）时很好用。我还见过有人用快慢指针判断回文链表，思路是先用快慢指针找中点，然后把后半段反转，再逐个比较。

4.2 左右指针：有序数组的两数之和问题

第二大类是左右指针，典型场景就是有序数组。经典题目是“两数之和 II - 输入有序数组”：给定一个升序数组和一个目标值，找到两个数使得它们的和等于目标值。暴力做法是两层循环枚举，O(n²)，但左右指针的做法是 O(n)。

vector<int> twoSum(vector<int>& numbers, int target) { int left = 0, right = numbers.size() - 1; while (left < right) { int sum = numbers[left] + numbers[right]; if (sum == target) return {left + 1, right + 1}; else if (sum < target) left++; else right--; } return {-1, -1}; }

这个方案的原理其实就一句话：数组有序，所以当和小于 target 时，说明当前左指针的数字太小，必须往右移动；当和大于 target 时，说明右指针的数字太大，必须往左移动。指针每一步都能排除一堆不可能的组合，所以总步数不会超过 n 步。

4.3 滑动窗口模板与最长无重复子串实战

滑动窗口是双指针里最常用、也最容易被“边界卡死”的一类。它的模板其实非常固定：右指针不断向右扩展窗口，当窗口内的条件不满足时，左指针向右收缩窗口，每一步记录当前窗口的最优答案。

以“无重复字符的最长子串”为例，这是面试中出现频率极高的滑动窗口题。思路是用一个哈希集合维护当前窗口内的字符，右指针每走一步，如果新字符已经在集合里，就不断移动左指针并删除左指针指向的字符，直到集合里没有这个新字符，然后把它加进去，更新答案。

int lengthOfLongestSubstring(string s) { unordered_set<char> window; int left = 0, ans = 0; for (int right = 0; right < s.size(); ++right) { while (window.count(s[right])) { window.erase(s[left]); left++; } window.insert(s[right]); ans = max(ans, right - left + 1); } return ans; }

我踩过最大的坑是“先扩展再收缩”还是“先收缩再扩展”的顺序搞反了。正确逻辑一定是：新字符来了以后，如果它已经在窗口里，你必须先把窗口收缩到不包含它，然后才能把它插入并更新答案。如果你先 insert 再收缩，那个重复字符就会被错误地算进窗口长度里。

滑动窗口还有一个变种是“固定窗口大小”，比如求长度为 k 的子数组最大平均值。这时候左右指针同步移动，本质上是“前缀和”或者“递推更新”的思路——每次窗口向右滑动一位，去掉最左边的，加上最右边的，复杂度同样是 O(n)，但代码逻辑比双端队列简单多了。

5. 常见问题与现场排查实录

5.1 排序算法的几个经典Bug排查

排序代码写错，最烦人的不是编译错误，而是面对一组数据“看似对但实际错”。我排错的时候第一件事就是打印left、mid、right三个边界值，看递归是否按预期切分。有一次我没打印，硬是花了二十分钟才发现是mid写成了(left + right) / 2，大数组直接溢出成负数。

排查堆排序的常见问题，我会用一个“手动构造小样例”的办法。比如手动给定一个[3, 1, 4, 1, 5]数组，我在纸上画完全二叉树，然后一步步走代码，比对第几次交换之后堆结构是否合法。这样能很快发现是建堆下沉写错了，还是交换后的下沉漏写了边界heapSize的更新。

还有一种很隐蔽的错：堆排序交换堆顶和末尾元素之后，如果忘记把堆的大小减一，那么“末尾已经排好的元素”会被再次下沉，数据就会被莫名打乱。这个问题在递归写法里尤其容易混，因为递归栈传参把heapSize传丢了。我建议变量名约定好，n表示原数组长度，heapSize表示当前堆的有效长度，千万不要混用。

5.2 滑动窗口为什么总是差一个数

滑动窗口题做错，十有八九是边界差一。比如“最长无重复子串”中，每次更新答案是在插入新字符之后还是之前，直接决定答案会不会漏掉最后一个字符。我自己的习惯是在每个 right 指向的新元素成功入窗后立刻更新ans，这样能保证所有右端点都被覆盖到，不会漏。

另外经常有人问：为什么是while收缩而不是if收缩？因为有时候左指针移动一次并不能消除重复，比如窗口里有“a b c a”，新来的a是重复的，你必须把 left 一路移动到第一个a的后面，中间可能删掉 b、c 等多个字符，所以用while才能彻底排除冲突。

5.3 自测方法与刷题心得

DAY4的复盘阶段，我用了一个“五分钟测试法”：写完代码先不着急跑样例，而是自己闭上眼睛，把数组在脑子里过一遍，代码跑一步，数组变一次，如果某一轮的状态和你预期不一样，立刻就能定位问题。这个方法对于递归、双指针、堆排序这种“操作在边界上移动”的算法特别有效。

另外一个建议是准备一个“错题本”，不用写长篇大论，就记录三个东西：题目类型、我写错的关键行代码、正确写法。我刷算法题到现在，本子上最常重复出现的错误其实是同一个——while条件里的边界比较符写反。这类错误光靠刷题很难纠正，但记下来每次写之前先看一眼，能显著减少返工时间。

6. 写在最后：这样打卡才不容易中途放弃

如果你也在用“DAY+主题”的方式做算法打卡，我的体会是：不要把每天安排得太满，一天两个算法主题再加每主题两道实战题，已经到极限了。贪多嚼不烂，堆排序和滑动窗口这两个知识点我DAY4当天消化完之后，DAY5又花了一天专门重写一遍，才算真正稳定。

另外我强烈建议你每学完一个算法就写一个“为什么它能工作”的小段落。不是写给别人看的，而是用自己的话把原理说清楚。比如归并排序为什么稳定？因为合并时遇到相等的元素我们优先取左半段的，保持了原顺序。这种输出倒逼输入的方式，比我刷十道题还有用。

今天就先分享到这里，我下一轮的DAY5打卡准备啃二分查找与贪心算法的组合应用，到时候会把“猜数字游戏”如何一步步演化成标准二分模板的完整过程记录下来，咱们到时候接着聊。