双指针解决数组分块：从移动零到颜色分类的完整框架

很多刷算法题的朋友应该都遇到过一种奇怪的感觉一道题当天看懂了题解代码也照着敲了一遍感觉会了结果过两天碰上一道“长得很像”的题又愣住了。双指针里的“数组分块”就是这类问题的典型代表。“数组分块”这四个字第一次听的人可能有点懵数组不是天然就是一块一块的吗分块又是分什么其实它描述的是一个非常常见的问题模式——把一堆元素按照某个条件重新排列拆成两个或多个区域。例如把所有零挪到末尾、把所有偶数放在前面、把比某个基准值小的元素搁左边……这类题在各类算法练习和面试真题里出现频率极高最常见的马甲就是“移动零”和“颜色分类”。这篇文章我想沿着一条更本质的线来讲先把“分块问题”的共同特征抽出来再拆双指针的两套经典模型然后用两道具体题目把细节磨透最后给一组写法对照和调试心得。不管你是刚开始刷题的新手还是刷了一阵子却总觉得“换汤就换药”的同学相信都能从里面拿到一套能直接用的框架。1. 数组分块指的是哪类问题1.1 分块问题的共同特征先别急着看代码我们先解决一个更根本的问题什么样的题目该往“数组分块”上想我习惯用一个很直白的判断标准题目是不是在要求“一个数组里的元素按自身属性被重新组织成若干连续区域”。拿移动零来说数组里有一堆非零数和一堆 0要求把 0 全部挪到数组末尾同时保持非零元素的相对顺序。翻译一下就是把数组分成两块——前一块全是非零后一块全是零两块都是连在一起的。再拿颜色分类来说数组里只有 0、1、2 三种数字要求排成000...111...222...的样子。这是分成三块。还有快排里的 partition给定一个基准值 pivot把小于它的元素放到左边大于等于它的放到右边。这是分成两块如果是三路快排则是分成“小于 / 等于 / 大于”三块。这类问题的共同特征我总结成三点只有一个数组整个过程没有真正意义上的“新增元素”和“删除元素”所有操作只是位置重排划分依据是每个元素自身的某个二值或三值属性比如“是不是 0”“是奇数还是偶数”“比 pivot 大还是小”题目通常要求原地完成或者至少不允许开一个等长数组再倒回去这对空间复杂度提出了明确约束。如果一道题同时满足这三条那你基本可以断定这是一道用双指针做数组分块的题。1.2 为什么不用计数排序这种“更简单”的做法有同学一定会问颜色分类为什么不干脆数一数 0 有几个、1 有几个、2 有几个然后直接按数量覆盖回去这样也是 O(n) 时间代码还更短。问得非常好。事实上计数排序确实能解决颜色分类这道题而且笔试里你这样写也不会被判错。但在实际练习和面试场景中理解双指针分块依然有不可替代的价值原因有三。第一分组依据不总是可枚举的有限值。如果数组里存的不是 0/1/2而是任意整数要求把所有小于某个 pivot 的放左边那你就没法“数一数有几个小于 pivot 的数”——当然可以先遍历一遍数出来但 pivot 一变计数就得重来。双指针则完全不需要预先知道每组的数量。第二面试官问颜色分类大概率不是想考你“会不会数数”。这类题真正考察的是原地一遍扫描的 partition 思想也就是你能不能在不借助额外数组的情况下用常数个指针把数组划分干净。这是快排、三路快排、滑动窗口等一系列高级技巧的底层能力。第三也是我个人觉得最重要的一点数组分块是双指针体系里最干净、最容易被彻底理解的一类入门题。把分块吃透后面学快排的 partition、学滑动窗口、学链表里的快慢指针都会顺很多。这也是为什么这个系列的第一篇选择从它讲起。2. 双指针分块的两套模型2.1 同向双指针维护一块连续的“已整理区”先说第一套模型同向双指针也叫快慢指针。两个指针都从数组左边出发一个跑得快一个跑得慢。在这种模型里两个指针各司其职慢指针left负责标记“分界线”也就是下一个应该被放进目标区域的元素该放的位置快指针right负责往前扫描逐个检查数组里的元素。整个逻辑非常像流水线上挑苹果right像传送带一个苹果一个苹果地送过来left像装箱工人的手只要看到合格品满足目标条件的元素就把它放到“合格品区”的末尾然后手的位置往前挪一格。用数组下标来描述就是[0, left)已经整理好的、满足目标条件的区域[left, right)已经被扫过、但暂时还留在原位的元素[right, n)还没被查看的元素。每次right往前走一步如果发现当前元素“该到前面去”就把它和left位置的元素交换然后left也往前走一步。形象一点说left就像一个不断向右推进的隔离墙把“合格区”和“待定区”隔开。这套模型的优点是它保留了元素的相对顺序因为每次都是把合格元素从右边“插”到左边合格区的尾部不会让合格元素之间发生穿插。2.2 相向双指针从两端同时往中间压缩第二套模型是相向双指针也叫碰撞指针。两个指针分别从数组的最左端和最右端出发向中间靠拢。这种模型的思想也很直观既然最终目标是把数组分成左右两个区域那不如直接让左指针负责找“不该待在左边的元素”让右指针负责找“不该待在右边的元素”两个人都卡住时说明这一对元素正好该互换。伪代码的感觉是这样left 0, right n - 1 while left right: 只要 nums[left] 已经在左侧区域就 left 只要 nums[right] 已经在右侧区域就 right-- 交换 nums[left] 和 nums[right]比如把偶数放前面、奇数放后面且不要求保持相对顺序时这个方法特别顺手左指针一直往右走遇到偶数就跳过直到碰到奇数停下右指针一直往左走遇到奇数就跳过直到碰到偶数停下然后交换两个指针同时往里收一步。相向双指针的缺点是交换会破坏同类元素之间的相对顺序。想象一排偶数和奇数穿插左边某个偶数被交换去右边时它可能越过右边其他偶数的原有顺序。所以一旦题目明确要求“保持非零元素的相对顺序”这类稳定性要求同向双指针通常是更安全的选择。2.3 循环不变量判断代码对错的核心很多题解在写完代码后会画一堆箭头标上“左边这块是 XXX右边那块是 XXX”。这些图背后有一个非常硬核的概念——循环不变量。循环不变量指的是在每一轮循环开始之前数组一定已经满足的某种固定结构。它不会因为循环的推进而失效每次循环结束这个结构又被重新恢复并且比上一轮更接近最终目标。为什么这个概念极其重要因为它直接决定了你的边界条件和交换逻辑。举个例子移动零要维护的结构是“[0, left)里全部是非零元素”。如果你在循环过程中发现某个操作会让这个区间里出现 0那就说明写错了。又比如颜色分类要维护的是“[0, i)全是 0[i, j)全是 1(k, n-1]全是 2”。每处理完一个元素你得检查这三条性质是否仍然成立。如果不成立立刻回头看代码。很多人写边界条件时靠猜比如到底写while (l r)还是while (l r)要不就是拿几个用例硬试。其实只要把不变量写清楚循环条件是可以推理出来的。下面这两道题我会反复演示这个推理过程。3. 由简入繁移动零的完整拆解3.1 题意转化把“移动零”翻译成分块移动零这道题标准描述是给定一个数组nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序并且必须原位操作。只看这句话可能会觉得“移动零”的重点是“移动”。但一旦你把视角换成数组分块题意就变成了把数组分成两块前一块全是非零元素后一块全是 0且非零元素的先后顺序不能变。这里有两个关键约束“保持非零元素的相对顺序”说明要稳定“原位操作”说明不能用额外数组。稳定 原位 两块划分这三个特征精准指向了同向双指针模型。那就用left和right两个同向指针来做。3.2 指针定义与代码实现指针定义如下left下一个非零元素应该放到的下标它同时也是“非零区域”和“已扫描区域”的分界线right当前正在扫描的元素下标。C 写法#include vector #include algorithm using namespace std; void moveZeroes(vectorint nums) { int left 0; for (int right 0; right nums.size(); right) { if (nums[right] ! 0) { swap(nums[left], nums[right]); left; } } }Python 写法def move_zeroes(nums: list[int]) - None: left 0 for right in range(len(nums)): if nums[right] ! 0: nums[left], nums[right] nums[right], nums[left] left 1代码就这么多不到十行。我们手动走一遍经典用例[0, 1, 0, 3, 12]初始left 0right 0数组[0, 1, 0, 3, 12]right 0nums[0] 0跳过right 1nums[1] 1交换nums[0]和nums[1]数组变[1, 0, 0, 3, 12]left 1right 2nums[2] 0跳过right 3nums[3] 3交换nums[1]和nums[3]数组变[1, 3, 0, 0, 12]left 2right 4nums[4] 12交换nums[2]和nums[4]数组变[1, 3, 12, 0, 0]left 3最终结果[1, 3, 12, 0, 0]非零相对顺序保持住了。3.3 为什么必须用 swap而不是直接赋值很多初学者会写成这样void moveZeroes(vectorint nums) { int left 0; for (int right 0; right nums.size(); right) { if (nums[right] ! 0) { nums[left] nums[right]; // 少了交换 left; } } }这段代码有没有问题它会把非零元素一个个放到前面去但问题是原来left位置的那个元素被直接覆盖掉了它可能是 0 也可能不是 0。如果是 0那 0 并没有被“移动”到末尾而是彻底丢失了——数组里的元素变少了一段逻辑值。最后结果可能变成[1, 3, 12, 12, 12]之类完全不对。正确做法是swap(nums[left], nums[right])。它的本质是把我手里的非零元素放到前面去同时把前面积压的 0或者尚未处理的元素换到后面来。这样每个元素都还在数组里只是换了个位置。另一种同样正确的思路是“覆盖 末尾补零”void moveZeroes(vectorint nums) { int left 0; for (int right 0; right nums.size(); right) { if (nums[right] ! 0) { nums[left] nums[right]; } } while (left nums.size()) { nums[left] 0; } }这种写法先把所有非零元素依次搬到前面再把剩下的位置统一填 0。它也很好理解缺点是必须区分“搬移”和“填零”两个阶段如果忘记第二个循环就会出现后半段残留旧值的问题。我个人更推荐swap版本因为一次遍历就完成语义也更贴近“分块交换”。3.4 边界用例与常见错误边界用例是验证分块代码的试金石。移动零至少要把下面几类情况都测一遍空数组[]循环直接不进入结果还是空数组单元素[0]或[5]不会发生交换也不会越界全是零[0, 0, 0]每次right都遇到 0left一直停在 0不需要移动一个非零夹在零里[0, 0, 1]最终变成[1, 0, 0]已经满足条件的数组[1, 2, 3, 0, 0]swap本身不会破坏已有顺序。我见过的高频错误主要有三种用赋值代替交换导致元素丢失忘记给left自增结果多个非零元素挤到同一个位置循环条件写成right nums.size() - 1漏掉最后一个元素。这三种问题只要在测试用例里加上“数组末尾是非零元素”的情况比如[0, 0, 3]基本立刻暴露。4. 从两块到三块颜色分类荷兰国旗问题4.1 三指针的分区设计移动零只是两块划分难度不高。真正能检验你理解深度的是颜色分类也就是荷兰国旗问题。题目描述很朴素给定一个只包含 0、1、2 的整数数组要求原地排序使得数组变成0...0, 1...1, 2...2的形式。两块划分用两个指针就够了三块划分需要三个指针。常见的命名是i、j、k为了避免和普通循环变量混淆我会强调它们的区域语义i0 区域的右边界[0, i)里的元素全部是 0j当前正在扫描的位置[i, j)里的元素全部是 1k2 区域的左边界(k, n-1]里的元素全部是 2[j, k]之间是还没处理的待定区域。循环条件是while (j k)。为什么是因为当j越过k的时候说明待处理区域已经空了左边是 0 和 1右边是 2数组已经分好块。C 实现#include vector #include algorithm using namespace std; void sortColors(vectorint nums) { int i 0; int j 0; int k nums.size() - 1; while (j k) { if (nums[j] 0) { swap(nums[i], nums[j]); i; j; } else if (nums[j] 1) { j; } else { // nums[j] 2 swap(nums[j], nums[k]); --k; // 注意j 不前进 } } }4.2 扫描到 0为什么 i 和 j 都要前进先看nums[j] 0的分支。当j这个位置发现一个 0它应该被送到 0 区域的末尾也就是i的位置。执行swap(nums[i], nums[j])后[0, i1)就全是 0 了。那j位置换过来的值是什么这取决于原来的nums[i]是什么。这就要用循环不变量来推理了[i, j)这个区间里全是 1如果i j那么原来的nums[i]一定是一个 1换到j位置后这里变成 1j后它正好落在新的[i, j)也就是 1 区域内如果i j说明 0 区域和扫描点重叠swap是自交换当前位置还是 0j后它落在新的 0 区域内。所以无论哪种情况交换后j位置的值只可能是 0 或 1绝不可能是 2于是可以放心让i和j同时推进不需要重新判断。4.3 扫描到 2j 为什么必须原地不动再看nums[j] 2的分支。执行swap(nums[j], nums[k])后我们把一个 2 放到了 2 区域的左边界外面也就是k位置然后k--这样(k, n-1]仍然是 2 区域。关键问题来了原来k位置上的元素被换到了j位置。这个元素我们完全没看过它可能是 0、1、2 中的任意一个。所以不能直接j把它跳过必须让j留在原地在下一轮循环里重新判断这个新来的值。这个分支是荷兰国旗问题最大的坑。很多人第一次写都会顺手在swap后写一个j结果得到的数组在某些用例下是错的。举个反例输入[2, 2, 0, 1]初始i0, j0, k3nums[0] 2与nums[3]交换得到[1, 2, 0, 2]k2如果此时错误地jj1继续循环nums[1] 2与nums[2]交换得到[1, 0, 2, 2]k1再jj2循环条件j k变成2 1不成立结束最终结果是[1, 0, 2, 2]中间 0 和 1 的顺序错了。如果第二分支没有错误j结果应该是[0, 1, 2, 2]。记住一句话在荷兰国旗问题里两个 2 交换过来的是未知元素未知元素必须被重新审视。这是“算法一旦需要回溯判断”的典型例子。4.4 三指针模型的边界用例颜色分类的边界测试也有固定套路[]k -1循环不进入没有问题[0]、[1]、[2]单元素数组[0, 0, 0]、[1, 1, 1]、[2, 2, 2]全同元素分组[2, 1, 0]需要跨区域交换[0, 1, 2]已经是目标状态看代码会不会因为“过度处理”而破坏有序性。尤其是最后一个用例非常考验代码的简洁性。如果某个分支在“本来就对”的情况下多做了一次多余交换就可能把一个已经分好块的数组重新打乱。5. 一组同类题的写法对照5.1 移除元素返回值就是分块边界题目给定一个数组nums和一个值val原地移除所有等于val的元素返回数组的新长度。这道题本质上就是“把不等于val的元素分到左边等于val的元素不管它们在右边怎么乱”。同样用同向双指针模板int removeElement(vectorint nums, int val) { int left 0; for (int right 0; right nums.size(); right) { if (nums[right] ! val) { nums[left] nums[right]; left; } } return left; }注意这里用的是赋值而非交换因为题目只要求返回新长度不要求保留等于val的元素在数组里的具体位置。赋值覆盖后[left, n)里残留的旧值不会被读取所以无伤大雅。这也说明了一个重要细节同一个模板要不要用 swap取决于题目的目标是否要求“另一块里的元素依然是有效值”。5.2 奇偶划分稳定还是不稳定选了不同模型再来看一道常见的奇偶排序题。如果题面写的是“把偶数放前面奇数放后面并且保持偶数之间的相对顺序、奇数之间的相对顺序”这就是稳定性要求应该用同向双指针加交换vectorint sortArrayByParity(vectorint nums) { int left 0; for (int right 0; right nums.size(); right) { if (nums[right] % 2 0) { swap(nums[left], nums[right]); left; } } return nums; }如果题目只要求“偶数放前面奇数放后面不要求保持相对顺序”那可以用相向双指针代码往往更短而且交换次数接近“必要轮换”的下限vectorint sortArrayByParity(vectorint nums) { int left 0, right nums.size() - 1; while (left right) { while (left right nums[left] % 2 0) left; while (left right nums[right] % 2 1) --right; if (left right) { swap(nums[left], nums[right]); left; --right; } } return nums; }很多同学在这道题上纠结“到底写没写对”其实真正需要先想清楚的是题面到底有没有“保持相对顺序”这半句话。这半句话直接决定了模型选择。5.3 快排 partition 也逃不出这两个模型如果你已经学过快速排序回看它的 partition 步骤会发现它恰好就是数组分块问题Lomuto 分区选一个 pivot用一个慢指针维护“小于 pivot 的区域”一个快指针扫描所有元素小于 pivot 的元素交换到左边。这几乎就是移动零的同构版本只不过判断条件从“是不是非零”变成了“是不是小于 pivot”。Hoare 分区两个指针分别从左右两端出发左指针找不该在左侧的 pivot右指针找不该在右侧的 pivot找到一对就交换。这完全是相向双指针。这也是为什么我说数组分块是底层能力理解了这两套双指针模型快排 partition 的很多写法你就不会再觉得是“另一套知识”而是同一个思想的自然延伸。5.4 四道题的写法对照表为了看起来更清楚我把上面四类题的建模信息放在一张表里。题目块数双指针模型循环不变量要点最关键的一个坑移动零2 块同向[0, left)非零right扫描别用赋值替代 swap 导致零丢失颜色分类3 块同向 右边界指针[0,i)是 0[i,j)是 1(k,n-1]是 2nums[j]2交换后不能j移除元素2 块同向[0,left)不等于 val返回值是 left不是数组真正长度奇偶排序稳定2 块同向 swap[0,left)是偶数用%2判断时注意负数的奇偶定义快排 Lomuto partition2 块同向[0,i)小于 pivot千万别在交换时忘了把 pivot 放回正确索引这张表做完你会发现一件事所谓数组分块核心就两句话——第一分几块第二稳定不稳定把这两个问题回答清楚代码自然而然就能写出来。6. 调试心得如何判断你写的分块代码是对的6.1 用循环不变量做运行时检查一个很实用的小技巧在刚写完分块代码、心里没底的时候临时在循环体里加一段“断言代码”检查当前数组是否满足不变量。比如移动零可以在循环里加一句for (int t 0; t left; t) { assert(nums[t] ! 0); }在 Debug 模式下跑几个用例一旦断言失败说明某个交换逻辑破坏了“[0, left)全部非零”的性质。颜色分类也可以类似检查for (int t 0; t i; t) assert(nums[t] 0); for (int t i; t j; t) assert(nums[t] 1); for (int t k 1; t n; t) assert(nums[t] 2);等所有用例都过了再把断言删掉换成正式提交。这个方法对新手建立“闭环调试”的感觉特别有帮助比你肉眼一行行读代码快得多。6.2 三个必测的边界类型根据我的经验分块代码翻车基本都集中在三类边界用例上。第一类是空数组和单元素数组。它们能很快暴露“循环条件 1 / -1”之类的越界问题。比如颜色分类里如果数组是空的k -1循环while (j k)不会进入但如果你把条件写成while (j k)并且在里面直接访问nums[k]就可能越界。第二类是全部元素都属于同一个块比如全 0、全 1、全 2。这种情况下代码应当几乎不发生交换如果你发现它疯狂交换多半是某个分支的分类条件写反了。第三类是已经排列好的数组比如[0,1,2]。这类用例最容易暴露“多余交换”问题。好的分块算法应该能做到当数组已经满足目标状态时循环不会进行任何破坏性操作。我印象很深的是有位同学写过一版颜色分类在[0,1,2]这样已经有序的输入上因为处理nums[j] 2的分支多写了一个j结果把结果改成了[0,2,1]。这种问题如果不用“已经有序”的用例去测真的很难发现。6.3 交换自交换的小心机还有一个很容易被忽略的细节当left right时swap(nums[left], nums[right])是自交换。C 的std::swap和 Python 的多元赋值都能正确处理自交换所以直接用没问题。但如果你为了“省一次交换”改成自己手写临时变量交换int tmp nums[left]; nums[left] nums[right]; nums[right] tmp;那在left right时也没有问题因为中间变量会完整传回。真正需要注意的是那些“三变量异或交换”写法在指针相等时可能直接把元素变成 0。所以我的建议很简单标准库的 swap 能搞定的事不要自己花式实现。6.4 什么时候别用双指针最后这部分也是我在实际带人时反复强调的数组分块用双指针是常规武器但不是所有这类题都只能用双指针。如果题目的分组依据是“数组里的值只能是有限的几种比如 0/1/2”那计数排序确实更短先数每种值出现几次再按顺序覆盖回去。时间复杂度同样是 O(n)额外空间是 O(1)因为值域大小固定。这时候双指针不是“唯一解”更多时候是被面试官期待的标准解。但如果数组的值域很大、或分组依据是“与某个动态 pivot 比较”双指针 partition 就是正解计数排序不管用了。我的判断标准是当你看到题面里出现“原地”“只遍历一遍”这类约束时基本就是双指针分块在向你招手当题面只要求“排序”且元素值域非常小、又没提空间限制时先想想有没有更直接的计数法也未尝不可。不迷信某一种套路也是算法能力的一部分。写到这里我其实想给你留一个最诚实的建议数组分块这类题代码短到不能再短但每一行都应该是从循环不变量里推出来的而不是从题解里背下来的。动手在纸上把分区图画出来把每个指针的语义写清楚再落代码出错率会低很多。移动零和颜色分类这两道题值得你隔一周不看任何提示重写一遍直到一次性通过所有边界用例为止。到那时候你会发现双指针系列的下一块拼图已经自己长出来了。