刷题刷到一定阶段你会发现LeetCode 27题“移除元素”几乎是所有人绕不开的一道题。它被标记为“简单”但恰恰是这种简单题最能看出一个人写代码的基本功。面试的时候我也经常拿这道题当开场题有人一分钟写完有人写完自己都解释不清指针为什么要这样动。今天就把这道题彻底拆开从双指针的原理推导到各种变体题的迁移思路再到实际面试里怎么说、怎么写、怎么避坑一次讲透。先明确一下我们要解决的是什么问题给定一个数组nums和一个目标值val原地移除所有数值等于val的元素返回移除后数组的新长度。要求不能使用额外的数组空间只能使用 O(1) 的额外空间元素的顺序可以改变而且不需要考虑数组中超出新长度后面的元素。如果你已经刷过题这三个要求你应该有感觉原地修改、O(1)空间、不用管新长度之后的内容这基本上就是在给你指路让你用覆盖的思路去解而不是新建数组拷贝。下面我把这道题的前因后果、代码实现、变体扩展和面试话术完整过一遍。1. 先想清楚移除元素到底在考什么1.1 拆题这道“简单题”的四个隐藏条件很多人做这道题上来就写了一个for循环 if判断遇到val就调用splice或者erase然后把数组长度减一。这种写法在力扣上也能过但如果你去面试面试官大概率会追问一句“你能保证它真的满足所有题目约束吗”第一个隐藏条件也是最容易忽略的必须原地修改。意思是不能新建一个数组把不等于val的元素收集进去再整体赋值回来。虽然很多判题系统对这一点检查不严格但题目本身明确说了只能使用 O(1) 的额外空间。新建数组是 O(n) 空间直接犯规。第二个隐藏条件返回值是数组的新长度而不是删除后的数组。题目让你返回一个整数后面的内容不用管了。这意味着你只需要把有效的元素全部挪到数组前面然后返回一个长度值就行后半段残留什么元素都无所谓。这个约束非常关键它是所有“覆盖型”解法的理论基础。第三个隐藏条件元素的顺序可以改变。这句话不是白写的。如果你用双指针从两端向中间夹逼交换元素会改变原有顺序但题目允许所以这也是一条完全合法的思路。很多人刷题时没注意到这句话白白放弃了一种更省操作次数的解法。第四个隐藏条件注意边界情况。数组为空、数组所有元素都等于val、数组所有元素都不等于val这三种情况代码必须要正确处理。空数组要返回 0全等于val要返回 0全不等于val要返回原数组长度且不能改坏数据。这些边界条件看着简单写错一个就是整个逻辑崩盘。四个条件叠在一起这道题其实就在考一个核心能力你能否在有限空间内通过元素之间的互相覆盖来完成一次“逻辑删除”。这是一切后续变体题的底层模型。1.2 为什么说它是“原地算法”的启蒙题如果你刚开始刷 LeetCode我建议你把这道题当成“原地算法”的必修课。所谓原地算法就是除了输入数据本身之外几乎不再额外消耗存储空间只能靠交换、覆盖、搬移来解决问题。这类算法在很多分布式系统、嵌入式环境、大数据场景里有实际意义因为在这些场景里额外开一块和原始数据一样大的内存可能意味着整任务失败。移除元素这道题恰好能把“覆盖”这个概念讲明白。你不需要真正“删掉”某个元素你只需要把需要保留的元素移动到数组前部然后告诉调用方有效长度是多少。后面残留什么谁也不会去看。这就像整理一张书桌老板只关心你交出的文件是否整齐码在最上面桌角还堆着什么废纸无所谓。一旦你掌握了这种“覆盖思想”后面遇到删除有序数组中的重复项、移动零、移除链表元素会发现它们全是同一个套路的小变种。所以这道题值得花时间去抠细节而不只是背一个答案。接下来我把最主流的解法从原理到代码完整过一遍。2. 双指针解法一种思路吃透一类题2.1 快慢指针是怎么推出来的移除元素最经典的解法是快慢指针也叫双指针中的“同向双指针”或“覆盖指针”。我们在没有任何额外空间的前提下想要把所有不等于val的元素挪到数组前端最自然能想到的方法就是一个指针负责“扫描”另一个指针负责“记录摆放位置”。我习惯把两个指针取名fast和slow。fast从头到尾遍历数组负责检查每个位置的元素是否等于val。slow指向“下一个应该放置保留元素的位置”初始时从 0 开始。当fast发现当前元素不等于val就把这个值复制到slow指向的位置然后slow往后移动一位。如果当前元素等于val就跳过它fast继续前进。这样做下来所有不等于val的元素都会被依次搬到数组前部slow的值正好就是保留元素的数量。最后返回slow就是新数组长度。举个直观的例子。假设数组是[3, 2, 2, 3]val 3。一开始slow 0fast 0看到nums[0] 3跳过fast变 1。接着nums[1] 2不等于 3执行nums[0] nums[1]数组变成[2, 2, 2, 3]slow变成 1fast变成 2。继续扫描nums[2] 2赋值给nums[1]数组变成[2, 2, 2, 3]slow变成 2fast变 3。最后一个nums[3] 3跳过。最终返回slow 2前两位是[2, 2]恰好是移除 3 之后的结果。这个过程中有个小细节很多人没意识到fast每次循环都会前进但slow只有在发生覆盖时才会前进。也就是说slow始终指向“保留区”的末尾。两个指针对同一段空间做操作一个负责探索一个负责落位整个过程就是典型的“读写分离”。2.2 三种主流语言的参考实现理解了原理写代码其实非常快。我平时刷题主要用 Python面试手写有时候用 Java偶尔前端同事会问 JavaScript 版本三种实现我都放在这里。Python 版本class Solution: def removeElement(self, nums: List[int], val: int) - int: slow 0 for fast in range(len(nums)): if nums[fast] ! val: nums[slow] nums[fast] slow 1 return slowJava 版本class Solution { public int removeElement(int[] nums, int val) { int slow 0; for (int fast 0; fast nums.length; fast) { if (nums[fast] ! val) { nums[slow] nums[fast]; slow; } } return slow; } }JavaScript 版本var removeElement function(nums, val) { let slow 0; for (let fast 0; fast nums.length; fast) { if (nums[fast] ! val) { nums[slow] nums[fast]; slow; } } return slow; };三个版本的逻辑完全一致只是语法层面的差异。时间复杂度是 O(n)因为fast指针完整扫描了一遍数组空间复杂度是 O(1)除了几个指针变量之外没有额外空间。这道题对时间复杂度其实没有更优的可能因为至少要遍历一遍数组才知道哪些元素要移除。2.3 最容易写错的地方覆盖时机代码本身不长但我在面试中见过无数人栽在一个看似不起眼的细节上到底什么时候该赋值、什么时候该移动slow有些人的写法是这样的for fast in range(len(nums)): if nums[fast] ! val: nums[slow] nums[fast] slow 1把slow 1写到了if外面。这样写的话即使fast指向的是等于val的元素slow也会继续增长。最后返回的slow不是有效元素个数而是一个被放大的错误值。数组前部也被错误覆盖结果全乱。记住一个判断标准slow的每次前进必须对应一个“被成功保留的元素”。如果判断条件不成立说明当前fast位置的元素要被丢弃不需要为它腾出位置slow自然也不应该动。这个逻辑理清了代码就不会写错。另外还有一个很容易被忽略的点当fast的元素赋给slow时如果fast和slow指向同一个位置赋值是自我赋值没任何问题。只有当fast领先于slow时覆盖才会真正发生。所以在[1, 2, 3, 4]这种没有任何val出现的数组里整个数组不会被搬动一次只是白白扫描一遍效率上没有任何额外开销。3. 进阶方向当“不允许改变顺序”时怎么办3.1 对撞指针的另一个经典套路移除元素还有第二种主流解法利用的是题目中“元素的顺序可以改变”这句话。思路是把不等于val的元素往前放等于val的元素直接和数组末尾的元素交换然后缩小尾部范围。初始化两个指针left指向数组开头right指向数组末尾。让left从头开始扫描如果nums[left] val就把nums[right]的值复制到nums[left]同时right左移一位。为什么可以直接覆盖因为被覆盖的元素已经被判定为“不需要保留”而right位置的元素还没被检查过把它搬过来继续处理即可。如果nums[left] ! val说明当前元素保留left右移。当left和right相遇时数组前半部分就是所有不等于val的元素left的值就是新数组长度。class Solution: def removeElement(self, nums: List[int], val: int) - int: left, right 0, len(nums) - 1 while left right: if nums[left] val: nums[left] nums[right] right - 1 else: left 1 return left这种解法有意思的地方在于它不会复制每一个保留元素而是直接把不要的元素“顶”到后面去。当数组里要删除的元素很少时对撞指针明显更高效。举个例子数组是[4, 1, 2, 3, 5]val 4快慢指针需要扫描完整数组而对撞指针第一轮就把nums[0]和nums[4]做了交换直接结束只操作了一次。3.2 到底该选哪种解法你在 LeetCode 上提交两种解法都能通过但在真实面试场景里选哪种取决于你对“稳定性”的需求以及后续题目会不会追加限制。快慢指针最大的优势是保持元素原有顺序。如果题目要求删除元素之后剩余元素的相对顺序不能改变那只能用快慢指针。对撞指针会改变顺序在某些题目里不允许但在移除元素这道题里是允许的。从操作次数上看如果要删除的元素很少对撞指针的交换次数更少如果要删除的元素很多快慢指针的覆盖次数也更少。代码风格上我个人的经验是快慢指针更通用因为它在“有序数组去重”那类题里有直接的迁移可能性而对撞指针更像“一次性技巧”。如果你两种都掌握了面试时先问清楚“顺序是否可以改变”然后决定用哪种会给面试官留下“考虑周全”的印象。4. 变体题从移除元素到一大批同源题4.1 283. 移动零把特殊值“清零”移动零这道题本质上就是把val 0的移除元素题加上一个“末尾补零”的动作。题目要求把数组里所有 0 移动到末尾同时保持非零元素的相对顺序。解法可以复用快慢指针的框架先遍历数组把所有非零元素按顺序覆盖到数组前部这一步和移除元素一模一样只是把val换成了0。然后在slow指向的位置之后把剩下的位置全部填成 0。class Solution: def moveZeroes(self, nums: List[int]) - None: 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.2 26. 删除有序数组中的重复项LeetCode 26题“删除有序数组中的重复项”和移除元素几乎是一个模子刻出来的。区别在于移除元素给定了一个明确的val而重复项问题要求“相邻且相等”的元素只能保留一个这个值不是提前给定的而是在扫描过程中动态确定的。解法还是快慢指针。用slow指向下一个不重复元素应该放置的位置用fast扫描整个数组。因为数组是有序的所以只需要判断nums[fast]是否等于nums[slow - 1]。如果等于说明是重复项跳过如果不等于就覆盖到slow位置然后slow前进。class Solution: def removeDuplicates(self, nums: List[int]) - int: slow 0 for fast in range(len(nums)): if slow 0 or nums[fast] ! nums[slow - 1]: nums[slow] nums[fast] slow 1 return slow这里有个细节第一次见到的时候估计会困惑为什么要判断slow 0因为当slow为 0 时nums[slow - 1]是nums[-1]在 Python 里是最后一个元素会出错。所以要么单独处理第一个元素要么像上面这样加一个短路条件。这个坑很经典属于刷题开荒必须要经历的一关。4.3 80. 删除有序数组中的重复项 II允许保留两个这道题是 26 题的强化版要求有序数组中的每个元素最多出现两次。只要把判断条件改一下立刻就能做出来。现在用slow指向下一个要放置元素的位置fast扫描时只需要判断nums[fast]是否等于nums[slow - 2]。如果等于说明当前元素至少会重复三次跳过如果不等于就覆盖到slow位置。为什么这样判断是对的因为数组是有序的如果nums[fast] nums[slow - 2]说明在slow - 2和fast之间至少已经有两个相同的元素了当前的nums[fast]是第三个相同的值必须跳过。如果nums[fast] ! nums[slow - 2]说明它和这个位置上的元素不一样一定不会导致同一元素出现三次可以放心保留。class Solution: def removeDuplicates(self, nums: List[int]) - int: slow 0 for fast in range(len(nums)): if slow 2 or nums[fast] ! nums[slow - 2]: nums[slow] nums[fast] slow 1 return slow这道题你看出规律了吗26题判断的是nums[fast] ! nums[slow - 1]80题判断的是nums[fast] ! nums[slow - 2]。允许保留 k 个重复项就把下标偏移改成slow - k。这类问题的通用解法就是这么总结出来的而不是一道题一个套路。4.4 203. 移除链表元素从数组到链表刷过链表相关的题就会知道leetcode热词里经常能看到“链表leetcode”而移除链表元素正是移除元素思路在链表结构上的延展。LeetCode 203题要求删除链表中所有等于val的节点。链表和数组不同它没法直接按下标访问也没有“新长度”的概念。但删除节点的核心思想是一样的跳过不需要的节点保留需要的节点。实现上需要用到虚拟头结点也就是哨兵节点来处理“头节点也可能被删除”的边界情况。class Solution: def removeElements(self, head: Optional[ListNode], val: int) - Optional[ListNode]: dummy ListNode(-1) dummy.next head prev dummy curr head while curr: if curr.val val: prev.next curr.next else: prev curr curr curr.next return dummy.next这里的dummy节点不是业务数据纯粹是为了统一删除头结点和非头结点的操作逻辑。如果你不用dummy就得单独写一个“如果头结点是val就移动头结点指针”的循环代码会多出一截还容易漏边界。这个技巧可以记下来几乎所有的链表删除类题目都能用上。5. 现场实战面试中的正确表演方式5.1 代码细节决定成败刷题刷多了你会发现真正的 diff 不在“会不会做”而在“能不能写得让面试官满意”。移除元素这道题虽然简单但代码细节上还是有几个点可以加分。第一变量命名别用i、j随手一写。刷题代码不需要过度讲究但fast和slow、left和right这种表意清晰的命名能让面试官一眼看出你的思路。我见过很多人在白板上写了一个i写到一半自己都忘了i是扫描指针还是保留指针。第二循环条件要写对。快慢指针通常用for fast in range(len(nums))这时候fast自然递增不容易出错。如果换成while fast len(nums)就一定要在循环体内手动让fast自增漏掉就死循环。对撞指针则要注意left right和left right的区别这个会直接影响边界元素是否被正确处理。第三注释不是必须的但关键判断最好顺口解释两句。比如你写if nums[fast] ! val可以说“fast 指向的元素需要保留所以放到 slow 的位置然后 slow 前进一步”。把思路说清楚面试官才知道你不是背的模板。5.2 常见错误与排查技巧实录我把这道题最常见的错误整理成了一张表按出现频率排序你可以自查一下自己踩过几个。错误类型具体表现原因分析解决办法慢指针自增位置错误slow 1写在 if 外面返回长度偏大没有理解 slow 只在“保留元素”时才前进把 slow 的自增缩进到 if 内部没有原地修改新建数组存放非 val 元素再复制回来没注意 O(1) 空间限制使用双指针覆盖不开新数组用remove/splice边删边遍历删除后元素前移跳过下一个待检查元素不了解动态操作数组对索引的影响用后端语言时直接覆盖不要真删对撞指针循环边界出错数组中间某个 val 没被处理或越界left right写成漏掉最后一个元素用具体小数组模拟一遍检查空数组或全删数组返回错误返回原数组长度而非 0没有对边界条件单独思考先想三个边界空、全删、全保留这里重点说一下“边删边遍历”这个坑。很多新手用 Python 会写类似这样的代码i 0 while i len(nums): if nums[i] val: nums.pop(i) else: i 1单看这段逻辑似乎没错但它有一个致命问题pop(i)之后后面的元素会整体前移一位此时如果不自增i下一次循环就会处理原先i1位置的元素这样刚好不会跳过。可是如果你用的是for循环那麻烦就大了——for i in range(len(nums))里的i每次都会自动加 1删除一个元素后紧跟其后的元素就被跳过了。这种情况在力扣上不是每次都能测出来但一旦测试用例里有连续两个等于val的元素结果必然出错。所以刷题的时候尽量养成“覆盖代替真删”的习惯这不仅是为了满足空间要求更是为了避免索引震荡的坑。5.3 从一道简单题建立刷题节奏最后聊点刷题方法论。很多人觉得简单题没价值一上来就啃难题结果越刷越挫败。我的经验是简单题反而是建立“解题原型”的最好材料。移除元素这道题值得你做到三件事第一不看题解手写出来第二把两种双指针解法都写一遍第三把 26、80、283、203 这四道变体题都用同一套思维过一遍。一旦完成这三步你的收获绝对不是一个题解而是一整套可以复用的“骨架”。以后再遇到“在数组中筛选保留某些元素”的需求你会第一时间想到快慢指针遇到“数据可以从两端向中间压缩”的需求会想到左右对撞遇到“链表删除”需求会想到哨兵节点。刷题就是这样比的不是谁题目刷得多而是谁能从有限题目里提炼出更多的模式。我个人实际面试中的一个体会是移除元素几乎不会作为独立题目出现它更多时候是作为后续题目的前置步骤。比如让你在有序数组中查找某个目标值你先通过双指针去掉无效数据再进入二分查找或者让你判断一个数组是否可以通过移除一个元素变成递增数组你依然需要先理解“什么情况下应该跳过某个元素”。把基础问题的本质搞明白后面的一切都是在它之上叠砖加瓦。
