数组分块双指针详解：从移动零到颜色分类

刷题时遇到“数组分块”这一类的双指针题，很多人都有过这样的经历：答案看一遍就懂，代码抄一遍就会，但关上题解，重写一遍就卡壳。尤其是“把0都挪到数组末尾”、“把奇数放左边偶数放右边”这类题，看起来人畜无害，一动手就暴露了对双指针底层逻辑的理解不足。这事儿的根源，在于大多数人只记住了fast和slow两个指针怎么动，却没回答最核心的那个问题：为什么这样动就能保证结果是正确的、高效的、且不需要额外空间。

这篇文章想把“双指针1（数组分块）”这个话题讲透，适合正在学算法基础、准备技术面试、或者想彻底弄明白移动零/颜色分类这类题目的读者。我会先把数组分块到底在分什么讲清楚，再推导双指针为什么是这个问题下的最优解，然后用完整的代码和逐步模拟拆解移动零这个最典型的题目，最后扩展去重、荷兰旗问题、快速排序partition这几个相似场景，并且把我自己在调试中踩过的坑和排查思路一并放进来。看完之后，你再看所有“原地整理数组”的题，思路应该会清晰很多。

1. 数组分块到底在分什么

1.1 分块的本质和题目的隐藏要求

所谓数组分块，就是把一个数组按照某种条件，重新划分为若干连续的区段。最常见的二段划分是：满足条件P的元素全部跑到数组的左半边，不满足条件P的元素全部跑到右半边。移动零这道题，条件P就是“元素不等于0”；奇偶分割这道题，条件P就是“元素是奇数”。两段之间不要求有序，每段内部也不要求有序，这是分块问题和排序问题的根本区别。

这一点很多初学者会忽略。普通排序要求全数组按照某种全序关系排列，比如从小到大，而分块只要求“每一块内部符合同一个性质，块与块之间有明确的边界”就行。举个例子，把数组[2, 0, 1, 0, 3, 0]按“非零在左，零在右”分块，结果为[2, 1, 3, 0, 0, 0]即可，[1, 2, 3, 0, 0, 0]也是合法结果。既然不要求内部排序，那如果解题时用了排序算法，本质上就是杀鸡用牛刀，复杂度从O(n)变成了O(n log n)，反而做差了。

再看题目的另一个通常约束：原地操作。原地操作的意思是空间复杂度要控制在O(1)，不能另外开一个数组来暂存结果。很多人的第一反应其实是“开一个新数组，把满足条件的按顺序放进去，再把不满足的放进去”，这做法完全正确，空间复杂度O(n)，但绝大多数平台会要求原地，原因是这类题目考的就是双指针的标记和覆盖技巧。如果允许开新数组，题目就失去了考察指针设计的价值。

用个生活里的例子来类比：衣柜里的衣服要按“常穿”和“不常穿”分两堆，如果你家里还有空抽屉，最简单是拿个空抽屉先放一堆，再放另一堆，这就是O(n)空间的做法。但如果条件是“只能在这个衣柜里腾挪，不能动其他抽屉”，你就只能像玩华容道一样，盯着当前要处理的那件衣服，找到空位换过去。双指针解决的就是后者。

1.2 为什么这类题目几乎都要求“保持相对顺序”

很多数组分块的题目里都藏着一条附加说明：保持非零元素的相对顺序（或者保持原顺序）。移动零如此，数组去重也要求保留重复元素中第一个出现的位置。这条要求直接把很多解法砍掉了。

如果不要求保持相对顺序，这题可以写得更简单：用两个指针一头一尾，左边找0，右边找非0，找到就交换，左右往中间逼近，一轮搞定。但一旦要求“保持相对顺序”，头尾指针法就不行了，因为把一个靠后的非零元素交换到前面时，中间那些非零元素的相对顺序会乱掉。

这个约束提醒我们：能用头尾双指针解决的，是“只分块、不保序”的弱版本；要求保序的，必须用快慢指针这种单向扫描的写法。快慢指针从左往右推进，每次只把“当前发现的非零元素”放到它该去的位置，后面的元素不会跳到前面来，相对顺序天然保持。这也是为什么移动零的标准解法全部是快慢指针，而不是头尾相向指针。

2. 双指针为什么会成为最优解

2.1 先看暴力做法慢在哪儿

如果不让用双指针，也不让用额外空间，你会怎么写移动零？最容易想到的暴力写法是：从左往右扫描，遇到0，就把后面所有的元素整体往前挪一位，然后把0放到数组末尾。这方法逻辑上没问题，但最坏情况下是O(n²)。考虑一个极端输入：[0, 0, 0, ..., 0, 1, 2, 3, ...]，前面大半段全是0。扫描到第一个0时，要把后面n-1个元素都挪一次；扫描到第二个0时，又要挪n-2个元素。累加起来接近n²/2次移动，输入规模到十万级别就跑不动了。

很多人说“那我先统计0的个数，再把非零元素依次往前填，末尾统一补0”，这确实能优化到O(n)，但写法上隐含了一个小陷阱：如果你在“把非零元素往前填”的过程中原地覆盖了尚未扫描的元素，可能导致数据丢失。为了避免丢数据，又容易绕回去开新数组。双指针的写法之所以优雅，是因为它把“找非零”和“找空位”这两个动作同时做了，不需要预统计，也不需要备份。

另一个常被想到的方案是排序。既然要让0全部到末尾，那把数组排个序，0自然就到末尾了。但排序改变了非零元素之间的相对顺序，而且整数排序是O(n log n)，在面试中会被直接追问：“你能不能做到线性时间、原地、稳定？”这一串要求排除了排序和开新数组，最后就只剩下双指针这一条路。这也是为什么说双指针是这类题的最优解，它同时满足了三个硬约束：O(n)时间、O(1)空间、保持相对顺序。

2.2 快慢指针为什么是线性的

快慢指针处理数组分块时，把整个数组在逻辑上划分成了三个区域：慢指针slow的左边是已经处理好的区域，里面全是满足条件的元素；快指针fast的右边是还没看的区域；slow到fast之间是“待定区”，里面可能有0也可能有非零，但还没被安放。这个三区间的视角非常关键，它能帮你写出准确无误的边界条件。

每次循环，fast只往右走一步，做一次判断。如果fast指向的位置发现了一个满足条件的元素，就把它和slow指向的位置交换，然后slow右移一位。如果fast指向的元素不满足条件，什么都不做，继续往后看。关键点在于：fast永远只往右走，不会回头；slow也永远只往右走，不会回头。每个元素最多被fast扫过一次，最多被交换一次，整体时间消耗就是O(n)。

那为什么slow不会回头？因为slow左边已经全是“合格元素”，它是下一个合格元素应该放置的插入点。一旦这个位置被填上，就得把插入点右移，如果slow不移动，下一个合格元素又会覆盖掉刚放好的位置，逻辑就崩了。你可以把slow理解成排队窗口的“下一个叫号位置”，来一个合格的人，窗口就往后挪一个，不接受插队，也不回退。

2.3 正确性的直观理解

空谈复杂度不如直接验证正确性。双指针解法可以用一个循环不变式来概括：每次循环开始前，slow之前的元素都已经满足条件，且相对顺序和原数组一致；fast已经扫描过的区域不会再有“漏网”的合格元素。循环不变式是写算法题时特别有用的自查工具——只要你证明了“初始成立、迭代保持、终止时成立”这三点，代码的正确性就站得住，不需要拿几十个用例去猜。

初始时slow = fast = 0，slow左边是空集，循环不变式天然成立。迭代过程中，fast往右走一步，如果发现了新合格元素，就放到slow位置，然后slow++，这时slow左边又多了一个合格元素；如果没发现，fast++，已经处理过的区域没变化。终止时fast越界，说明整个数组都被扫描过，slow左边是所有合格元素，右边自然全是非合格元素，分块完成。

还有一个值得注意的细节是稳定性。快慢指针这套做法不会改变合格元素之间的相对顺序，原因很简单：合格的元素是从左往右被逐个安放进数组前段的，后出现的合格元素只会放在先出现元素的后面，不会跳到前面去。这在“移动零”题里表现为非零元素的相对顺序不变，在“数组去重”题里能保证不重复元素的先后关系不变。

3. 实战拆解：以“移动零”为例

3.1 完整代码与逐行解析

先看看最经典的移动零题目，需求是把所有0移动到数组末尾，同时保持非零元素的相对顺序，必须原地完成。下面这段代码是我实际一直在用的实现：

def move_zeroes(nums): slow = 0 for fast in range(len(nums)): if nums[fast] != 0: nums[slow], nums[fast] = nums[fast], nums[slow] slow += 1 return nums

这段代码短得不能再短，但每一行的信息量都很大。slow是下一个非零元素应该放的位置，初始为0，表示数组开头。fast用for循环从0扫到末尾，负责逐个检查。当nums[fast] != 0时，说明找到了一个合格元素，把它和slow位置的元素交换。交换之后slow自增，把插入点往后挪。

很多人会问，为什么是非零才交换，不是遇到0才处理？因为快指针的任务就是“找合格元素”，找到就往前提。遇到0等于找到了不合格元素，它不需要处理，因为它最终会被后面某个非零元素交换走，或者一直留在原地等被覆盖。这个视角转变很关键：不要想“怎么把0挪到后面”，要想“怎么把非零挪到前面”，0的位置是自然被挤出去的。

3.2 用具体输入模拟一遍指针移动

拿一个容易出错的输入来走一遍流程：nums = [0, 1, 0, 3, 12]。

初始状态：slow = 0，fast = 0。

fast=0时，nums[0] = 0，不满足条件，不交换，fast++。此时数组不变：[0, 1, 0, 3, 12]，slow还是0。

fast=1时，nums[1] = 1，满足条件，交换nums[0]和nums[1]，得到[1, 0, 0, 3, 12]，slow变成1，fast++。

fast=2时，nums[2] = 0，不满足条件，不交换，fast++。数组保持[1, 0, 0, 3, 12]，slow还是1。

fast=3时，nums[3] = 3，满足条件，交换nums[1]和nums[3]，得到[1, 3, 0, 0, 12]，slow变成2，fast++。

fast=4时，nums[4] = 12，满足条件，交换nums[2]和nums[4]，得到[1, 3, 12, 0, 0]，slow变成3，循环结束。

模拟下来可以看到一个很有意思的现象：slow和fast指向同一个位置时，交换的是元素自身，比如最后一步nums[2]和nums[4]，因为此时nums[2]已经是0，交换后12被放到下标2，下标4的位置变成0，12从“待定区”进入了“合格区”。而如果数组开头没有0，slow和fast会同步前进，交换的是自己和自己的值，相当于一次无效交换，但不会出错。这个“自己换自己”的情况在性能上有一点点浪费，但在正确性上完全无害，我见过有人为了省掉这次自交换把代码写得很复杂，实际上没必要，保持代码清晰更重要。

3.3 为什么慢指针只增不减

这是初学者最容易想不通的地方。假设现在slow指向的是某个位置，这个位置左侧已经有slow个非零元素了，现在fast找到了一个新的非零元素，把它交换到了slow位置，那么slow必须右移。因为再往右看，如果在slow位置再放一个非零元素，原来的非零元素就要被覆盖，那就丢了数据。

换个角度理解：slow左边是一个已经“验收完毕”的干净区，slow是干净区和待定区之间的一堵墙。墙左边全部合格，墙右边还没整理。墙壁只能往后推，因为如果你把墙往前挪，等于把已经验收合格的区域重新划入待定区，那之前的工作就白做了。如果你把墙往后推得太多，又会把尚未验收的元素圈进合格区，那里面可能还藏着应该被移到后面的0。

也正因为如此，slow的最终值刚好就是非零元素的个数。遍历结束后，slow左边全部是非零，slow右边全部是0，而数组长度是固定的，所以0的个数自然是len(nums) - slow。这个性质在扩展题里很有用，比如后续要确定“非零元素占多少位”，不用再额外统计一遍。

3.4 两种主流写法的边界对比

移动零的解法在讨论区还有很多变体，看得多了容易混乱。我把最常见的两种写法梳理一下，它们的核心思想一致，但边界处理有差异。

第一种是我上面写的“交换式”写法，遇到非零就把nums[fast]和nums[slow]交换，然后slow++。这种写法的好处是绝对不会读到未初始化的位置或者覆盖还没扫描的数据，即使slow和fast重合也无所谓。坏处是有时候会对同一个元素做一次无意义的自交换，比如数组本来就没有0时，fast和slow同步递增，每次都和自己交换，浪费一点常数时间。

# 写法一：交换式 def move_zeroes(nums): slow = 0 for fast, x in enumerate(nums): if x != 0: nums[slow], nums[fast] = nums[fast], nums[slow] slow += 1

第二种是“直接赋值”式写法：遇到非零，直接覆盖到slow位置，nums[slow] = nums[fast]，然后slow++。这种写法存在一个隐患：如果slow < fast，那nums[fast]被读取后，原位置的数值在数组中仍然存在，但这个位置的旧值可能会导致后面的逻辑错乱，除非扫描结束后统一把slow后面的所有位置补0。

# 写法二：覆盖+补零 def move_zeroes(nums): slow = 0 for fast in range(len(nums)): if nums[fast] != 0: nums[slow] = nums[fast] slow += 1 for i in range(slow, len(nums)): nums[i] = 0

两种写法都正确，但“交换式”更贴近“双指针同时维护两个区域”的本质，也更容易扩展成阵颜色分类那种三段分块的写法。如果你的目标是彻底理解双指针而不只是过题，推荐优先掌握交换式写法，然后自己动手把第二种也写一遍，感受两种写法在边界条件上的差异。

4. 相似题型与延伸：从两段到三段

4.1 两段分块的题型对照

理解移动零之后，你会突然发现一大片题目都在同一个框架内：划分成“满足条件块 + 不满足条件块”，条件块保持在左，快慢指针单向扫描。我把最常见的几类整理成了一张对照表，方便横向比较。

数组去重这题尤其适合在掌握移动零之后刷，因为它的写法几乎就是移动零的翻版，只是“交换”变成了“覆盖”。给定一个有序数组，要求原地删除重复元素，使每个元素只出现一次。你可以直接写成：

def remove_duplicates(nums): slow = 0 for fast in range(1, len(nums)): if nums[fast] != nums[slow]: slow += 1 nums[slow] = nums[fast] return slow + 1

这里的slow指向的是最后一个保留元素的位置，和移动零里“下一个位置”的定义略有不同，但这正是练习指针语义的好机会。两道题放在一起对照，你会发现核心永远是那三块区域：已完成、待处理、未探索。

4.2 三段分块：颜色分类问题

两段分块搞明白后，下一步自然就是三段分块。经典的颜色分类问题给一个只含0、1、2的数组，要求原地排序成0在最左、2在最右、1在中间。这个问题的解法用的是三个指针：left负责维护0区域的末尾，right负责维护2区域的开头，i负责遍历中间未处理的区域。

def sort_colors(nums): left, i, right = 0, 0, len(nums) - 1 while i <= right: if nums[i] == 0: nums[left], nums[i] = nums[i], nums[left] left += 1 i += 1 elif nums[i] == 2: nums[right], nums[i] = nums[i], nums[right] right -= 1 # i 不增加，因为换过来的值还没检查 else: i += 1 return nums

注意看这里有个关键差异：当nums[i] == 0时，交换后i要自增，因为left位置交换过来的数字，要么是1，要么是0，但不会是2。为什么？因为如果left位置之前是2，那它在更早的轮次里早就被右边处理掉了。而当nums[i] == 2时，交换后i不自增，因为从right位置换过来的数字可能是0、1、2里的任意一种，必须留在原地再判断一次。这个“换到2不前进、换到0前进”的细节，是很多人写颜色分类时容易写错的点。

如果你拿这个三指针方案回头去看移动零，会发现移动零其实是颜色分类的一个特例：只有0和非0两类，所以只需要维护一个左边界，不需要右边界。理解了这套递进关系，数组分块的双指针就算真正打通了。

4.3 快速排序partition的隐藏联系

数组分块的思想往深处走，就是快速排序里的partition。每一轮partition做的事情，本质上就是把数组分成“小于基准值的部分”和“大于等于基准值的部分”，左边满足条件，右边不满足条件，这和移动零不是一回事吗？

以经典的挖坑填数partition为例，基准值取最左边的数，用一个指针从左往右扫，遇到小于基准值的就往左填，最终基准值落在中间，左边全小于它，右边全大于等于它。这个过程的核心，也是数组分块里的“合格元素提前、不合格元素后置”逻辑。如果你能熟练写移动零的交换式代码，再看快排partition会轻松很多，因为它们的循环不变式几乎一模一样，只是把“非零”这个条件换成了“小于基准值”。

这个联系值得反复体会，因为面试中如果有人问你“快速排序是怎么保证O(n log n)的”，最终都要落到partition这个步骤上。而所谓的“随机化快排”，优化的也是partition时基准值的选取策略，底层还是数组分块。

5. 常见问题与排查技巧实录

5.1 四个最典型的坑

数组分块的双指针代码虽然短，但易错点一点也不少。我复盘了自己带过的人写这类题时的常见问题，总结出四个高频坑。

第一个坑是slow的语义定义不清。有人把slow定义为“当前已满足条件元素的最后一个位置”，有人定义为“下一个应放位置”。这两种定义在初始化和自增时的写法完全不同。如果你用的是后一种定义，初始化是0，交换后自增；如果你用的是前一种定义，初始化要设成-1，找到元素后先自增再交换或者先交换再自增。代码里规范不统一，就很容易出现差一错误。

第二个坑是循环边界写错。快慢指针的fast一般从0到len(nums)-1，很多人会顺手写成while fast <= len(nums)-1，如果同时在里面做着fast++，没问题，但如果用了for循环没注意范围，就可能多访问一个越界下标。尤其在三指针的颜色分类里，边界是i <= right而不是i < right，一旦把等于号漏掉，最后一个元素就永远不会被检查。

第三个坑是交换顺序问题。有的写法先slow++再交换，这就会导致第一个满足条件的元素没有被放到正确位置，而是跳到了第二个位置。我见过很多人调试半天，结果就是在交换和自增这两行的顺序上栽了跟头。

第四个坑是“自己换自己”时的心理负担。当数组开头连续几个元素都满足条件时，slow和fast指向同一个位置，交换是自己和自己，很多人会觉得“这有问题”，于是自作主张加了很多复杂判断，反而把代码写坏。实际上自交换是无害的，只要你不介意这点多余的常数时间，根本不需要特别处理。

5.2 用边界输入自查代码

代码写完后，我会建议至少跑三组边界输入来验证：

• 全零数组，比如[0, 0, 0]。这时fast遍历完，永远不会触发交换，slow始终是0，数组不变，但结果应该还是[0, 0, 0]，正确。
• 无非零数组，比如[1, 2, 3, 4]。这时每个元素都触发交换，slow和fast始终同步，每次都自交换，最终数组不变，正确。
• 空数组和单元素数组。空数组直接什么都不做，单元素数组如果它是0就不交换，如果非0就自交换一次，都不会错。

这三组输入加上一个混合输入[0, 1, 0, 3, 12]，基本能把绝大多数实现问题逼出来。如果在这几组用例下都正确，代码的逻辑基本就没问题。如果出了问题，先检查slow的自增位置、循环条件、交换顺序这三个点，90%的bug都在这里。

5.3 面试中如何把双指针讲清楚

如果你是在面试现场写这道题，除了把代码写对，表达也很重要。我会建议按照这个顺序讲：

先定性：“这是一个数组原地分块问题，目标是分成非零区和非零区，需要保持相对顺序”。然后报出设计思路：“我用快慢双指针，快指针负责扫描所有元素，慢指针维护下一个非零元素应该放置的位置，这样每个元素最多被访问一次，时间O(n)，空间O(1)。”接着写代码的时候，顺序不要乱，边写边解释循环不变式：“在每一轮迭代中，slow左边全是非零元素，fast右边全是未访问元素。”最后，准备一个复杂度证明和一个正确性说明。

很多面试官还会追问：“如果不想保持相对顺序，你会怎么写？”这时候把头尾双指针的交换写法拿出来讲就行，顺便解释两种写法的取舍，会显得你理解得比较透彻。这道题能聊得这么细，比单纯背答案肯定要好得多。

我在实际带人刷题时发现，移动零这道题真正写明白的人，往往不是因为代码写得快，而是因为在纸上能画出那个三区段的图，能说清楚为什么slow只增不减，为什么快指针遇到0不处理。这套东西如果还没形成肌肉记忆，建议不要急着往下刷难题，先在[0, 1, 0, 3, 12]这种输入上老老实实模拟三遍，再动手改写几种变体。把移动零内化成自己的东西，后面碰到的所有数组分块题，都会简单不少。