前阵子在刷题练习时又把 LeetCode 27 这道“移除元素”翻出来做了一遍。说实话这道题难度标着“简单”但我在实际刷题和模拟面试里见过不少人栽在上面有人一上来就del导致索引越界有人用了额外数组忘了题目要求 O(1) 空间还有人写出双指针却解释不清楚为什么返回slow就是新长度。这篇文章就围绕“移除元素”这一个题从暴力解法的缺陷开始逐步推导到双指针方案再把边界条件和面试追问整理出来。适合刚开始刷算法题的读者也适合准备面试、想把自己对数组原地操作的思路讲清楚的人。先明确一个很多人忽略的点这道题说的“移除”不是让你真的把数组变短而是把数组中不等于val的元素全部挪到数组前面然后返回“有效前缀”的长度。数组本身的长度并没有改变只是前 k 位是需要保留的元素后面的值是什么无所谓。理解了这一点双指针的写法就顺理成章了。1. 从题目原文看“移除”的真正含义1.1 原题描述与前置约束LeetCode 27 的题目描述大致是这样给你一个数组nums和一个值val你需要原地移除所有数值等于val的元素并返回移除后数组的新长度。额外要求是不要使用额外的数组空间必须使用 O(1) 额外空间修改输入数组。题目还给了一个提示元素的顺序可以改变不需要考虑数组中超出新长度后面的元素。这里每一句话都很关键。最容易踩的坑就是“不要使用额外的数组空间”。有些解法很自然会把不等于val的元素收集到一个新列表里再复制回原数组代码是能跑通的但空间复杂度变成了 O(n)不符合题目要求的原地修改。这种错误在 LeetCode 上依然能 AC因为判题只看最终的nums数组前 k 位和返回值不会检查你是否偷偷用了额外数组。但在面试中面试官一眼就能看出问题。“元素的顺序可以改变”这个条件也容易被忽略。很多国内版本的翻译会写成“元素的顺序可以改变”这意味着我们可以用更激进的覆盖策略比如首尾指针交换法。可如果面试官改了一个条件明确要求“保持相对顺序不变”那策略就必须变成快慢指针。所以读题阶段多花十秒钟能省后面不少麻烦。还有一个隐藏信息“不需要考虑数组中超出新长度后面的元素”。这句话的意思是我们不需要把数组后面对应位置的旧值清空也不用恢复成初始状态。比如原始数组是[3,2,2,3]val 3最终你返回2只要nums[0]和nums[1]都是不等于 3 的值通常是2和2后面的[3,3]无所谓。如果不理解这一点有人会尝试用pop()或resize真的把数组缩短反而把简单问题复杂化。1.2 输出的两个产物这道题表面上只要求返回一个整数但实际提交时系统会同时检查两样东西返回值和数组前 k 位的内容。你可以在本地测试时打印nums[:k]来验证结果LeetCode 后台也是类似逻辑。打个比方你有一箱水果要求把烂果子挑出来。你不需要把箱子物理变小只需要把好果子全部挪到箱子前面的位置烂果子丢到后面。最后你告诉别人“这一箱有 k 个好果子”人家只需要拿前 k 个出来用后面那些烂果子不会影响计数。这就是“原地移除”的本意。这个理解直接决定了代码结构。在写任何解法之前心里要有两个目标让所有不等于val的元素出现在数组开头 k 个位置上。返回这个 k。一旦能清晰说出这两个目标后面不管用什么指针方案代码都不容易写乱。2. 双指针方案快慢指针的完整推导2.1 暴力移除为什么不可取很多新手第一次见到这道题会尝试“逐个删除”。比如用 Python 的list.remove或者del思路是找到一个val就删掉一个直到数组里不存在val。这种做法至少有三个问题。第一在循环中动态修改数组长度会导致索引错乱。for i in range(len(nums))的循环次数在进入循环时就已经固定但删除元素后len(nums)变小后面的索引可能超出范围。第二list.remove在内部会移动后续所有元素时间复杂度是 O(n)如果有 k 个val最坏情况会到 O(n^2)。第三这不是在“原地筛选”而是在利用语言自带的数据结构操作面试时很难体现出算法思维。还有一种看起来靠谱的暴力写法每次遇到val就把后面所有元素整体向前移动一位。核心逻辑是这样def remove_element_brutal(nums, val): i 0 while i len(nums): if nums[i] val: # 把 i 之后的所有元素前移一位 for j in range(i, len(nums) - 1): nums[j] nums[j 1] # 最后一个位置已经没有意义直接弹出 nums.pop() else: i 1 return len(nums)这段代码能跑但性能很差。最坏情况是数组里全是val外层循环每轮都要把剩余元素全部搬一次每轮搬动长度分别是 n-1、n-2、...总操作次数接近 n^2/2。LeetCode 可能因为数据量不大直接 AC但这显然不是合格算法。面试官问你“能不能优化到 O(n)”如果你回答不上来这题就算砸了。暴力解法最大的贡献是帮我们确认了一个直觉如果每次删除都让“后面的元素排队往前挪”成本太高。那么能不能不挪那么多答案是可以因为题目根本不关心数组后半部分是什么。我们可以把“有效的非 val 元素”全部抄到前面跳过所有 val。这就是双指针方案的核心思想。2.2 快慢指针的复制逻辑快慢指针的代码非常短短到很多人背下来了却解释不清楚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用两个指针fast指针负责遍历原数组中的所有元素它的任务是在数组里“寻找”不等于val的元素。slow指针负责记录“下一个非 val 元素应该放到哪个位置”。每一次fast扫到一个不等于val的值就把它复制到slow指向的位置然后slow向右移动一格。如果fast遇到val什么都不做直接跳过。举个例子nums [0,1,2,2,3,0,4,2]val 2。手动模拟前几个回合fast 0nums[0] 0不是val复制到slow 0slow1。fast 1nums[1] 1不是val复制到slow 1slow2。fast 2nums[2] 2等于val跳过slow不动。fast 3nums[3] 2等于val跳过。fast 4nums[4] 3复制到slow 2slow3。继续执行最终slow 5数组前 5 位依次是[0,1,3,0,4]。为什么不担心覆盖掉还没检查的元素因为在整个过程中fast总是大于等于slow。当fast指向后面某个元素并复制到slow位置时slow所在的位置要么已经被处理过要么就是fast自己绝不会覆盖一个仍在等待检查的原始元素。这保证了算法在“边走边覆盖”的过程中不丢失状态。这个循环不变量很值得在面试时说出口每一轮循环开始之前nums[0:slow]中所有的元素都已经确认不等于val循环结束时slow的值就是非 val 元素的总数。2.3 为什么双指针是标准答案时间复杂度是 O(n)因为fast指针只把数组完整扫一遍。空间复杂度是 O(1)因为所有修改都在原数组上完成只用了两个整数变量。这题的“标准答案”之所以是快慢指针最重要的一点是它能保持元素的相对顺序。如果题目后续改成“要求移除后元素原来的相对顺序不变”唯一稳妥的写法就是这个。很多面试官会故意在 follow-up 里加这个限制目的就是想看你是不是只会背代码还是真的理解指针职责。快慢指针还有一个可以优化的细节。当数组开头本来就没有val时例如nums [1,2,3,4]val 5每一次复制操作都是nums[slow] nums[fast]而且此时slow fast相当于把元素赋值给自己白白做了一次写操作。数据量大时这不是致命的但确实不优雅。可以加一个判断def remove_element(nums, val): slow 0 for fast in range(len(nums)): if nums[fast] ! val: if slow ! fast: nums[slow] nums[fast] slow 1 return slow这样在slow fast时不触发赋值直接移动指针。这个优化在实际工程里也有意义减少无意义的写操作对缓存更友好。虽然它的常量优化很小但能在面试中体现出你对“读写开销”的敏感度。3. 允许乱序时的优化首尾指针法3.1 交换/覆盖式的思路题目如果明确说“元素的顺序可以改变”还有另一套更“暴力”的思路左右两根指针同时向中间移动遇到val就从数组尾部挪一个元素过来充数。先看代码def remove_element_two_pointers(nums, val): left, right 0, len(nums) - 1 while left right: if nums[left] val: nums[left] nums[right] right - 1 else: left 1 return left核心逻辑一句话left永远指向左边待检查的位置。如果这个位置的值正好等于val就用nums[right]覆盖它同时right向左移动一格。注意这里不能同时让left右移因为从右边拿过来的元素还没有被检查它可能也是val。下一轮循环会重新检查nums[left]。如果nums[left]本来就不是val那left可以放心右移。这个写法的巧妙之处在于被覆盖以后留在nums[right]位置的值已经没有意义了因为right已经不再参与后续扫描。换句话说我们只是把右边一个“还没有判断过”的值搬到左边来至于原来的val副本直接丢在数组后面的垃圾区。还是用nums [0,1,2,2,3,0,4,2]val 2走一遍left 0nums[0] 0不等于valleft 1。left 1nums[1] 1不等于valleft 2。left 2nums[2] 2等于val用nums[7] 2覆盖right 6。此时nums[2]仍然是 2但来源变了。left 2再次检查发现nums[2] 2等于val用nums[6] 4覆盖right 5。这次nums[2] 4。left 2nums[2] 4不等于valleft 3。后面继续最终返回left 5。可以发现一个特点只有当遇到val时才发生写操作遇到非val时只移动指针。所以如果数组中val出现次数很少这种写法比快慢指针执行更少的赋值操作。3.2 与快慢指针的取舍对比首尾指针法和快慢指针法都是 O(n) 时间和 O(1) 空间但它们有不同的适用场景。我整理了一个简单对比对比维度快慢指针首尾指针指针方向同向移动相向移动是否保持相对顺序保持不保持可能打乱主要写操作时机每个非 val 元素都赋值每个 val 元素被覆盖代码可读性更容易理解需要注意 left 是否前进适用条件不限通用性强仅在允许乱序时使用如果你只是刷题我会推荐优先写快慢指针。原因有两个第一它不依赖“顺序可以改变”这个条件在任何变体里都能用第二解释起来更流畅。首尾指针虽然在特定数据下写操作更少但“从右边搬来的元素可能也是 val所以 left 不能动”这个点很多人写着写着就漏掉了导致结果出错。首尾指针还有一个容易踩的边界问题循环条件必须用left right而不是left right。比如数组只有一个元素[2]val 2如果条件写成初始left right循环根本不会进入函数直接返回 0。这里恰好是对的但如果是[2]val 3也会直接返回 0这就是错的因为数组中明明有 1 个不等于 3 的元素。所以才能保证最后一个元素也被检查到。如果面试中只需要你写出其中一个强烈建议先把快慢指针写对再提一句“如果允许乱序我还有一个首尾指针的优化版本”。这样既能体现方案的多样性又不会因为写复杂版本而翻车。4. 边界条件与现场测试的策略4.1 五类必测用例写完代码后第一个验证对象不是 LeetCode 的测试用例而是你脑子里那组“极端情况”。边界条件能暴露绝大部分实现错误尤其是双指针类的数组题。我平时会固定测试这几类场景示例期望结果作用空数组[],val10防止 right 初始为 -1 造成越界全部要删[2,2,2],val20验证返回值正确归零全部保留[1,2,3],val43验证不丢任何元素目标在首尾[2,3,2],val21首尾指针的交换场景连续重复[1,2,2,2,3],val22验证连续 val 的跳过逻辑单元素且不等[2],val31最容易漏掉的场景如果用的是首尾指针法尤其要测试单元素且不等于 val 的情况。因为循环条件是left right当left right时必须进入循环判断只有这样才能返回正确结果。你可以用[2], val3心算一遍left0, right0nums[0] ! 3所以left1循环结束返回 1正确。另一个容易被忽略的测试是“目标值出现在末尾且恰好被 right 指针指到”。比如nums [1,2,3]val 3。用首尾指针最初right就指向一个val但没有关系因为从右边覆盖左指针时这个位置会被直接丢进垃圾区不会参与后续判断。真正需要担心的是覆盖到 left 上来的值依然是val所以用 while 循环反复检查 left 直到它不是 val 或左右指针交错。4.2 为什么不能用list.remove/del实现不少人在现场写代码时会写出这种版本def remove_element_wrong(nums, val): i 0 while i len(nums): if nums[i] val: nums.pop(i) else: i 1 return len(nums)这段代码用 Python 的pop实现了删除部分测试用例能过。但有两个问题。第一pop(i)是 O(n) 的操作因为它需要把i后面的元素全部左移。外层循环最坏也是 O(n)综合起来就退化成 O(n^2)。第二你完全绕开了本意要训练的“原地覆盖”思想只是调用了语言内置功能。假如面试官让你用 C 语言写你不可能像 Python 那样直接 shrink 数组最终还是要回到双指针。更经典的错误版本是nums [1, 2, 3, 2, 4] for i, x in enumerate(nums): if x 2: del nums[i]这种“遍历时删除自身元素”的写法在 Python 里会直接跳过某些元素。因为enumerate生成的是实时索引当你删除索引为 1 的元素后原本索引为 2 的元素会变成索引 1但循环的下一次迭代会直接从索引 2 开始导致一个元素被漏检。这不是算法问题而是对语言内建机制理解不到位。刷题阶段犯这种错很正常但要在面试前彻底改掉。正确做法是明确告诉自己这道题里的“删除”是一个抽象概念真正的操作只能是“用保留元素覆盖到前面”而不是物理删除。5. 从刷题到面试我在这个题上总结的几点经验5.1 面试先问清楚顺序要求在实际面试中拿到这道题不要立刻低头写代码。先确认几个场景问题会让面试官觉得你很有经验“这个数组是可变长的吗允许原地修改吗”“要求保持元素原来的相对顺序吗”“返回值之外数组里需要保留什么”“数组元素有可能是负数吗长度可能为 0 吗”有人会觉得问这些问题多余但在面试里这是加分项。因为题目描述可能故意省略一些边界说明或者面试官临时口头加一个约束。如果你只按 LeetCode 默认条件写很可能把首尾指针写出来但面试官明明想要的是“保持顺序”那就偏离了预期。我习惯先问一句“相对顺序是否可变”再决定用哪种指针方案。如果允许乱序我会优先提首尾指针优化如果不允许我就直接写快慢指针并在注释里把循环不变量写清楚。5.2 代码书写的三个习惯第一个习惯是给指针起有意义的名字。别用i和j至少用slow/fast或者write/read。这能让你自己在写代码时思路更清晰向面试官解释时也更准确。比如slow表示下一个写入位置fast表示当前读取位置一句话就能讲明白。第二个习惯是写循环不变量。在代码开头或循环前加一行注释比如“nums[0:slow]始终是不等于 val 的元素集合”。这个注释不是给机器看的是给面试官看的。它说明你不是凭感觉写的代码而是有意识地维护一个逻辑条件。第三个习惯是写完以后立刻手动跑一个短样例。不用真的启动编译器在脑子里走一遍就行。我会选[0,1,2,2,3,0,4,2]这种目标值分散在中间和末尾的用例因为它的覆盖过程比较典型。只要返回值和数组前缀符合预期代码基本没问题。5.3 由这一题带出的同类题型“移除元素”不是孤立出现的题。一旦掌握了“原地数组筛选”的快慢指针模板很多题都能直接套用。LeetCode 26. 删除有序数组中的重复项快慢指针关键是判断当前元素是否和前一个已保留元素相同。LeetCode 283. 移动零快慢指针把非零元素复制到前面最后末尾补零或者用首尾指针把零扔到末尾。LeetCode 203. 移除链表元素换成链表后需要处理头结点和虚拟头结点的问题但本质也是“跳过目标节点重新拼接指针”。这类题共同的特点是在同一个数据结构上做“筛选”不能依赖额外容器空间要求 O(1)。一旦你习惯用write和read两个指针来思考问题再遇到类似的“原地删除、原地去重、原地移动元素”题目就不需要重新想一套方案。最后分享一个小习惯刷这类题不要满足于提交通过建议把每一轮slow/fast的状态打印出来观察指针移动和数组值变化。我之前写首尾指针版本时就是因为打印中间状态才发现自己在右指针指向val时会多走一次无效交换。这种细节普通题解很少会写出来但恰恰是真正动手敲过代码的人才会遇到的。把这题彻底吃透后面一整套原地数组操作题都会顺畅很多。