LeetCode 第 27 题《移除元素》是数组类题目的经典入口很多人觉得它简单但把双指针原地覆盖和首尾交换优化放一起对比时就能看到算法设计里关于数据移动、顺序保持和边界控制的微妙取舍。这篇文章会把两种策略掰开揉碎从最朴素的暴力解开始推导出双指针的写法再把它和首尾交换的变体放在同一个基准下做实测最后落到面试和应用场景里怎么选型。如果你正在刷题准备面试或者想搞懂这类“原地修改数组”题目的通用套路这篇文章应该能帮你省掉不少试错时间。1. 先吃透题意移除元素到底在考什么1.1 题目还原与输入输出规则《移除元素》描述起来很短给你一个数组nums和一个值val你需要原地移除所有数值等于val的元素并返回移除后数组的新长度。不要使用额外的数组空间必须仅使用 O(1) 额外空间并原地修改输入数组。元素的顺序可以改变不需要考虑数组中超出新长度后面的元素。这最后两句话是重点。“顺序可以改变”直接放松了约束给“首尾交换”策略留下口子而“不超过新长度后面的元素不用考虑”意味着我们只需要保证前 k 个位置上的元素是合法的后面残留什么旧值都无所谓。很多人在读题时忽略了这两句于是自然无法理解为什么可以有那么多种不同解法。举个例子nums [3, 2, 2, 3], val 3函数返回 2且nums前两个元素可以是[2, 2]。至于下标 2 和 3 的位置上仍然保留着原来的 3这是允许的。国内 OJ 与 LeetCode 的行为一致判题时只检查返回值对应的前缀部分。1.2 暴力解法的局限拿到题第一反应可能是遍历数组遇到等于val的元素就把它删掉。Python 里直接用list.remove()或者切片拼接确实能过但这会引发两个问题。第一个问题是时间复杂度。remove()的实现从列表头部开始查找找到后把后面的所有元素向前移动一位最坏情况下每次删除都是 O(n)整体复杂度达到 O(n^2)。del nums[i]同样是 O(n) 的移位操作。当数组长度到达十万、百万量级这种写法就完全跑不动了。第二个问题是“原地”的语义。nums [x for x in nums if x ! val]这种写法虽然简洁但它是创建了一个新列表再整体赋值给nums在 Python 里这属于替换引用本质上是 O(n) 的额外空间并不满足 O(1) 空间要求。哪怕面试官不较真这也属于“作弊解”。所以题目的真正考点是如何在一个数组里通过有限的元素移动做到“原地”把所有目标值剔除干净。这里浮现出来的第一个工具就是双指针。1.3 为什么大家一上来就想到双指针双指针在数组、链表、字符串题目里太常用了。它的核心思想是用两个游标或者两个下标协同遍历一个负责“读”一个负责“写”。对于移除元素这个场景直觉上很像“扫雷”读指针一路往右探遇到正常元素就给写指针写指针把元素放到前面安全区。读指针探查整个数组写指针标记安全区的边界。这种思路在工程上也有对应物比如实时日志系统里清理无效记录一个进程负责扫描原始流另一个进程负责把有效记录写入新的缓冲区两边一个追一个写互不干扰。只不过在数组里扫描和写入都发生在同一块内存上需要保证写指针不会覆盖还没扫描到的元素。好在这道题里写指针永远在读指针左侧所以天然安全。一旦理解了双指针的读写分离逻辑后面的代码就顺理成章了。2. 双指针原地覆盖最直观的解法藏着这些边界细节2.1 快慢指针的核心逻辑这里我更喜欢叫“快慢指针”因为“双指针”描述的是结构“快慢”描述了速度关系。慢指针slow代表下一个可以写入的位置快指针fast遍历整个数组。伪代码是这样slow 0 for fast in range(n): if nums[fast] ! val: nums[slow] nums[fast] slow 1 return slow逻辑非常清晰当fast指向的元素不是val就把它复制到slow指向的位置然后两个指针同时前进如果fast指向的元素是val就跳过它只有fast前进。slow最终停在最后一个有效元素的下一个位置所以返回slow就是新数组长度。这里最妙的特性是slow之前的元素一定都是非val元素因为每次写入前slow一定指向一个“废弃”位置被丢弃的旧值或已被覆盖过的位置写完后slow继续维护这个边界。这个性质叫循环不变式面试时如果能用一句话说明白印象分会很高。2.2 Python 代码与逐步模拟直接给出实现def remove_element(nums, val): slow 0 for fast in range(len(nums)): if nums[fast] ! val: nums[slow] nums[fast] slow 1 return slow拿nums [0, 1, 2, 2, 3, 0, 4, 2], val 2走一遍会得到这样的变化过程步骤fastslow当前数组仅看 slow 前内容动作初始-0[]-100[0]0 ! 2写入 nums[0]0slow1211[0,1]1 ! 2写入 nums[1]1slow2322[0,1]2 2跳过432[0,1]2 2跳过542[0,1,3]3 ! 2写入 nums[2]3slow3653[0,1,3,0]0 ! 2写入 nums[3]0slow4764[0,1,3,0,4]4 ! 2写入 nums[4]4slow5875[0,1,3,0,4]2 2跳过最终返回 5数组前五位是[0, 1, 3, 0, 4]后面残留[2, 2]也无所谓。可以看到所有非目标元素都被顺序保留在原数组中没有任何一对元素发生交换。2.3 边界条件与容易翻车的错误第一类错误是循环里把slow放错了位置。有人会写成if nums[fast] val: continue else: nums[slow]...逻辑没错但continue会跳过slow的递增吗其实只要slow只放在else分支就不会错。最容易出错的其实是把slow初始化为 1然后试图从第 0 个元素开始判断。比如slow 0 for fast in range(1, len(nums)): ...这样第一个元素根本没有被检查只有当数组每个元素都非val时结果才碰巧正确一旦第一个元素等于val整个结果就错了。正确做法是fast必须从 0 开始与slow同起点。第二类错误是返回值与数组长度的混淆。函数要求返回“新长度”但后续的数组内容会通过引用被外部感知。如果你返回slow 1在val不存在时就会多算一个位置导致输出包含未定义的数据。第三类错误是在 for 循环内修改nums的长度。比如if nums[fast] val: nums.pop(fast)这会让fast的索引追踪变乱还会导致 O(n^2) 的复杂度。记住原地数组题目里for 循环遍历的是逻辑长度不要做物理删除。2.4 时间复杂度与空间复杂度的账这个解法只遍历数组一次每个元素访问常数次时间复杂度 O(n)只用了固定数量的额外变量空间复杂度 O(1)。它赋值操作的数量等于非val元素的个数极端情况下如果没有任何元素等于val每个元素都会被复制一遍等于做了 n 次赋值。这看起来是“最少的时间复杂度”但并不是“最少的赋值操作”。这引出了一个有趣的话题当数组里要删除的元素很多时我们能不能减少赋值次数答案就是首尾交换优化。3. 首尾交换优化用“换”代替“覆盖”减少数据搬迁3.1 另一种思路把要删除的丢到尾巴去既然题目允许元素顺序改变那就不必追求“保留原来的相对顺序”。我们可以像整理一摞牌一样把不想要的牌往牌堆底部扔想要的牌留在上面。具体来说维护一个头指针和一个尾指针。头指针从左往右找一旦碰到等于val的元素就把尾部指针所指的元素拿过来放到这个位置然后尾指针左移。如果尾指针那边也是val下一次循环再处理。这样的好处是真正做“移动”操作时我们是从尾部补了一个有效元素过来而不是把后面所有元素都往前搬。被删除的元素并没有经过复杂的搬迁而是直接暴露在尾部区域等待被覆盖。3.2 代码实现与循环不变式稍微具体一点def remove_element_swap(nums, val): left 0 right len(nums) while left right: if nums[left] val: nums[left] nums[right - 1] right - 1 else: left 1 return left这里right并不是有效的数组下标它表示有效区域的右边界不含初始值是len(nums)。循环条件是left right只要左边还没有检视到右边边界就继续处理。当nums[left] val时用nums[right - 1]覆盖掉这个位置同时right--因为尾部那个元素已经移走了。如果nums[left] ! val就把left因为它已经是有效元素。这个写法和常见的“头尾指针”写法略有不同但更好理解循环不变式在循环中[0, left)区间内的元素全部非val而(right, n-1]区间内的元素是从尾部“填过来”的已处理元素。当循环结束时left right那么[0, left)就是所有有效元素返回left即可。3.3 为什么它比“覆盖”更省赋值操作双指针覆盖策略里碰到一个需要跳过的val时只是跳过什么都不写。但碰到一个非val元素时却要把它写到slow指向的位置。这意味着如果数组里没有val它会把每个元素都写一遍尽管什么都没删。首尾交换策略则不同。只有当nums[left] val时才做赋值而且是把后面的元素补过来。遇到非val元素时只移动left指针不碰数据。于是赋值操作的总次数等于“被删除元素的数量”而不是“被保留元素的数量”。设想极端情况一个长度为 100 万的数组其中 99 万个都是要删除的val双指针覆盖几乎要把数组重写一遍而首尾交换只需要补几次就能把所有val用尾部有效元素替换掉赋值次数少很多。我实际测过在大规模数据下两者耗时差距可能达到数倍。不过要注意这里的赋值次数对比是基于最坏情况的“写操作”数量不是总操作数所以也不代表首尾交换一定更快要结合测试数据看。3.4 一个容易被忽略的坑交换后新来的元素仍可能等于 val首尾交换逻辑里最经典的坑是当nums[left] val时我们执行nums[left] nums[right-1]这个新放过来的元素本身也可能等于val。如果这时候直接left就会漏掉这个元素导致结果不干净。比如nums [2, 2, 3], val 2。初始left0, right3。nums[0] 2把nums[2] 3放到位置 0然后right2。如果此时left变成 1再去检查nums[1]发现是 2又会补一次最终结果没问题但更糟的情况是如果尾部补过来的恰好也是 2比如nums [2, 2, 2]第一次补过来nums[2]还是 2第二次再补nums[1]还是 2第三次left0, right0退出循环返回 0也算对。但如果你在补完后立即left比如把代码写成nums[left] nums[right-1]; right-1; left1那么当补过来的元素等于val时就会被跳过最终返回的长度会偏大且包含val。我的习惯是把这第三种情况单独用注释标注不要移动left因为刚补过来的元素还没被检查过。这是很多教科书不会强调的细节却正是面试官有可能追问的点为什么你补完之后不前进left4. 两种策略的实测对比不只是快和慢的问题4.1 统一评测环境与测试用例设计为了有说服力我搭了一套简单但公平的测试。生成不同长度、不同删除概率的数组分别调用两个函数统计耗时、赋值次数和返回结果。环境是 Python 3.10Windows 11本机 CPU 中等水平计时使用time.perf_counter()每组重复 10 次取中位数。测试维度有这么几组数据特征期望val出现比例场景说明[0..n-1]且 val n10%没有删除元素[0..n/2)重复多组 val50%一半需要删除全部等于 val100%删除所有元素随机 0-100val50约 1%稀疏删除随机 0-3val2约 25%中等删除4.2 耗时与赋值次数结果分析先给结论在“没有删除元素”的场景双指针覆盖的赋值次数是 n首尾交换的赋值次数是 0。所以耗时上首尾交换明显更快。下面是 n100000不删除任何元素的一组典型结果策略耗时毫秒赋值次数双指针覆盖2.31100000首尾交换0.420但在“100%都是要删除元素”的场景两种策略都需要遍历整个数组最后都返回 0耗时差异变小因为首尾交换每次也会用尾部元素覆盖一个位置赋值次数也等于 n。不过双指针覆盖这里只需要一直跳过根本不需要赋值反而更快。很反直觉对吧真正有区分度的是稀疏删除场景。比如随机 0-100val50大约 1% 的元素需要删除n100000。双指针覆盖大约会复制 99000 个元素首尾交换则只复制约 1000 个元素。后者明显占优。如果把“保留相对顺序”当作一项指标双指针覆盖是唯一保证顺序不变的首尾交换会把尾部元素拉到前面顺序完全打乱。这直接影响题目变体如果题目改成“保持其余元素的相对顺序”首尾交换的做法就不符合要求了。4.3 有序性保持两者最大的行为分水岭顺序保持这个问题很多人没意识到它的工程意义。比如一个数组代表“排队序号”和对应的值删除某些人后剩下的人不能随意变更顺序否则排队逻辑就乱了。再比如数据流里每条记录有写入时间过滤时如果乱序下游处理会出问题。所以选型时要先回答三个问题删除后是否需要保持相对顺序删除比例高还是低数组中是否存在“尾部多删”的情况如果要求保持顺序直接选双指针覆盖如果不要求顺序且删除比例高选首尾交换更省事务。如果删除比例极低两者差别不大我更倾向于双指针覆盖因为代码更容易写对。4.4 选型建议什么时候用覆盖什么时候用交换我用一张表总结自己实际做题时的决策参考约束条件推荐策略原因必须保持原顺序双指针覆盖只有它能保持相对顺序顺序无要求val 数量较多首尾交换减少赋值数量顺序无要求val 数量很少双指针覆盖或首尾交换均可差别不大选可读性高的数组长度小1000任意性能差异可忽略写清晰即可数组不可整体覆盖但可变双指针覆盖避免尾部值被重复检查的极端情况当然LeetCode 的判题并不关心你是否保持顺序两种解法都能通过。但工作中如果处理的是真正的业务数组顺序往往是隐含约束所以不要无脑追求“最省赋值”的方案。5. 从一道题看一类题快慢指针与交换法的通用套路5.1 快慢指针家族移除元素、去重、移动零《移除元素》的双指针覆盖法换个条件就能套用到好几道经典题。第一个是“删除排序数组中的重复项”。数组已排序要求原地删除重复出现的元素使每个元素只出现一次返回新长度。解法几乎一模一样slow指向不重复区的最后一个元素fast遍历当nums[fast] ! nums[slow]时slow然后把新值写入nums[slow]。区别只在比较对象是nums[fast]与nums[slow]而不是与固定值val相比。第二个是“移动零”。要求把数组里的 0 移到末尾同时保持非零元素的相对顺序。也可以用双指针fast遍历遇到非零就写到slow最后把slow之后的位置全部填 0。本质上就是“先移除元素0再补位”只是一次扫描后额外做一次清零。第三个是“删除排序链表中的重复元素”链表场景换成指针操作思想依然不变。你可以在刷题时把这些题放一起对比会发现它们共享同一个循环不变式[0, slow)是已处理好的区域[fast, n)是待扫描区域。只要抓住这个不变量不同变体之间的差异只是判断条件不同。5.2 交换法家族原地哈希、荷兰国旗、数组旋转首尾交换的思想并不止于“移除元素”它在原地哈希、荷兰国旗问题、数组旋转等问题里也非常常见。原地哈希类的题比如“找到数组中消失的数字”通过交换把每个数放到它该去的位置nums[i]应该放到nums[nums[i]-1]一边交换一边修正位置最后缺失的位置自然暴露出来。这和首尾交换的“把尾部元素补到前面”不同但也属于利用交换在有限空间内完成数据重排的策略。荷兰国旗问题要求把红白蓝三色按顺序排列标准解法就是用三个指针left,right,cur当遇到红色和蓝色时分别交换到左右两侧本质上也是对区间进行边界划分。移除元素的首尾交换其实可以看作荷兰国旗的一个极简版只有两种元素“等于 val”和“不等于 val”一个头指针、一个尾指针把等于 val 的交换到尾部。数组旋转题中的“三步翻转法”也是交换法先整体翻转再分别翻转前半部分和后半部分完成原地旋转。这些题目背后的共同逻辑是用指针标记区域的边界用交换或覆盖维护边界避免开辟额外空间。5.3 把这道题扩展成工程场景日志清理、配置过滤刷题不只是为了面试很多想法在工程里也能落地。比如清理一批日志记录要求把所有级别等于DEBUG的日志移除同时保留相对顺序那双指针覆盖的思路可以直接套用到数组或列表上。如果不在意顺序只希望节省内存带宽可以考虑交换法。再比如配置文件的过滤有一份配置项列表需要删除所有标记为deprecated的项并要求剩余项的展现顺序不能乱这本质上就是一个“保持顺序的原地过滤”。如果直接用 Python 的列表推导式它新建列表然后原变量重新绑定但如果这是一个大到内存吃紧的环境双指针覆盖法的原地思路就有价值。再扩展一步数据库迁移脚本里常见的“原地清洗字段”把某列中不符合规则的值替换为NULL或者“合法默认值”如果必须保留行顺序也可以用双指针覆盖的思路只不过写入的目标是字段而不是数组元素。5.4 刷题之外的思考最优解不等于唯一解很多人刷题有个坏习惯看到题目立刻背出“双指针”答案然后草草提交。这道题如果只记住双指针覆盖法就错过了另一个很棒的思路。面试官问“还有没有别的做法”时能把首尾交换讲清楚并且说出两者适用的场景差异才算真正理解。最优解不是唯一的它取决于约束条件是否要求顺序稳定、删除比例高低、数据规模大小、内存访问模式。在 LeetCode 的评测体系里长度可能不会超过十万两种解法都很快但如果你把同样的问题搬到嵌入式环境、大文件处理上赋值的次数就成了关键指标。理解背后的“为什么”远比背模板重要。我在实际面试中遇到过类似题目候选人很流利地写出快慢指针但当被问到“为什么慢指针之前所有元素都是有效的”时有人能立刻用循环不变式解释有人支支吾吾说“反正就这样”。能把一道简单题讲出深度往往比解出一道难题更打动面试官。最后再分享一个小技巧写这类双指针循环时U 仔细观察while循环的退出条件。覆盖法用for遍历很舒服但交换法必须用while并且把“补过来之后不移动左指针”这一步想清楚。你可以在这两种解法上方各加一行注释写明白循环不变式再让面试官讲解这比把代码背下来有用得多。