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

很多刷算法题的朋友应该都遇到过一种奇怪的感觉：一道题当天看懂了题解，代码也照着敲了一遍，感觉会了；结果过两天碰上一道“长得很像”的题，又愣住了。双指针里的“数组分块”就是这类问题的典型代表。

“数组分块”这四个字，第一次听的人可能有点懵：数组不是天然就是一块一块的吗？分块又是分什么？其实它描述的是一个非常常见的问题模式——把一堆元素按照某个条件重新排列，拆成两个或多个区域。例如把所有零挪到末尾、把所有偶数放在前面、把比某个基准值小的元素搁左边……这类题在各类算法练习和面试真题里出现频率极高，最常见的马甲就是“移动零”和“颜色分类”。

这篇文章我想沿着一条更本质的线来讲：先把“分块问题”的共同特征抽出来，再拆双指针的两套经典模型，然后用两道具体题目把细节磨透，最后给一组写法对照和调试心得。不管你是刚开始刷题的新手，还是刷了一阵子却总觉得“换汤就换药”的同学，相信都能从里面拿到一套能直接用的框架。

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(vector<int>& 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 = 0，right = 0，数组[0, 1, 0, 3, 12]
right = 0，nums[0] == 0，跳过
right = 1，nums[1] == 1，交换nums[0]和nums[1]，数组变[1, 0, 0, 3, 12]，left = 1
right = 2，nums[2] == 0，跳过
right = 3，nums[3] == 3，交换nums[1]和nums[3]，数组变[1, 3, 0, 0, 12]，left = 2
right = 4，nums[4] == 12，交换nums[2]和nums[4]，数组变[1, 3, 12, 0, 0]，left = 3

最终结果[1, 3, 12, 0, 0]，非零相对顺序保持住了。

3.3 为什么必须用 swap，而不是直接赋值

很多初学者会写成这样：

void moveZeroes(vector<int>& 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(vector<int>& 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都遇到 0，left一直停在 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，为了避免和普通循环变量混淆，我会强调它们的区域语义：

i：0 区域的右边界，[0, i)里的元素全部是 0；
j：当前正在扫描的位置，[i, j)里的元素全部是 1；
k：2 区域的左边界，(k, n-1]里的元素全部是 2；
[j, k]之间是还没处理的待定区域。

循环条件是while (j <= k)。为什么是<=？因为当j越过k的时候，说明待处理区域已经空了，左边是 0 和 1，右边是 2，数组已经分好块。

C++ 实现：

#include <vector> #include <algorithm> using namespace std; void sortColors(vector<int>& 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, i+1)就全是 0 了。那j位置换过来的值是什么？这取决于原来的nums[i]是什么。

这就要用循环不变量来推理了：

[i, j)这个区间里全是 1；
如果i < j，那么原来的nums[i]一定是一个 1，换到j位置后，这里变成 1，j++后它正好落在新的[i', j')（也就是 1 区域）内；
如果i == j，说明 0 区域和扫描点重叠，swap是自交换，当前位置还是 0，j++后它落在新的 0 区域内。

所以无论哪种情况，交换后j位置的值只可能是 0 或 1，绝不可能是 2，于是可以放心让i++和j++同时推进，不需要重新判断。

4.3 扫描到 2：j 为什么必须原地不动

再看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]：

初始i=0, j=0, k=3
nums[0] == 2，与nums[3]交换，得到[1, 2, 0, 2]，k=2
如果此时错误地j++，j=1，继续循环
nums[1] == 2，与nums[2]交换，得到[1, 0, 2, 2]，k=1
再j++，j=2，循环条件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(vector<int>& 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 奇偶划分：稳定还是不稳定，选了不同模型

再来看一道常见的奇偶排序题。如果题面写的是“把偶数放前面，奇数放后面，并且保持偶数之间的相对顺序、奇数之间的相对顺序”，这就是稳定性要求，应该用同向双指针加交换：

vector<int> sortArrayByParity(vector<int>& 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; }

如果题目只要求“偶数放前面，奇数放后面，不要求保持相对顺序”，那可以用相向双指针，代码往往更短，而且交换次数接近“必要轮换”的下限：

vector<int> sortArrayByParity(vector<int>& 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]`是 2	`nums[j]==2`交换后不能`j++`
移除元素	2 块	同向	`[0,left)`不等于 val	返回值是 left，不是数组真正长度
奇偶排序（稳定）	2 块	同向 + swap	`[0,left)`是偶数	用`%2`判断时注意负数的奇偶定义
快排 Lomuto partition	2 块	同向	`[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 就是正解，计数排序不管用了。

我的判断标准是：当你看到题面里出现“原地”“只遍历一遍”这类约束时，基本就是双指针分块在向你招手；当题面只要求“排序”且元素值域非常小、又没提空间限制时，先想想有没有更直接的计数法也未尝不可。不迷信某一种套路，也是算法能力的一部分。

写到这里，我其实想给你留一个最诚实的建议：数组分块这类题，代码短到不能再短，但每一行都应该是从循环不变量里推出来的，而不是从题解里背下来的。动手在纸上把分区图画出来，把每个指针的语义写清楚，再落代码，出错率会低很多。移动零和颜色分类这两道题，值得你隔一周不看任何提示重写一遍，直到一次性通过所有边界用例为止。到那时候，你会发现双指针系列的下一块拼图，已经自己长出来了。