刷题平台上一道简单的“移除元素”曾经让我在面试现场差点翻车。题目很短给一个数组和一个目标值把所有等于目标值的元素原地移除返回新的长度。我第一反应就是“for 循环加 erase”结果一道看似送分的题面试官连环追问“你确定 erase 是 O(1) 吗”“数组顺序可以改变这句话你能怎么利用”让我意识到这题考的不是会不会写循环而是能不能理解删除的本质、有没有双指针的思维。这篇我把这道题从头拆到尾包括暴力解为什么容易错、快慢指针和首尾双指针的取舍、以及它和移动零、删除重复项这类题共通的骨架希望能帮你把这类“原地过滤”题目一次吃透。1. 先看清题目在考什么原地、顺序可变、返回长度1.1 原始题意和几个容易被忽视的字眼LeetCode 27 题“移除元素”的原文是这样给你一个数组nums和一个值val你需要原地移除所有数值等于val的元素并返回移除后数组的新长度。要求不使用额外的数组空间只能使用 O(1) 额外空间。更关键的一句是元素的顺序可以改变并且不需要考虑数组中超出新长度后面的元素。这句话里信息量很大。首先“原地”意味着你不能新建一个数组把不等于val的元素装进去再输出。其次“顺序可以改变”给了你很大的操作自由度——也就是说你可以用后面的元素覆盖前面的元素不必为了保持原顺序而做大量搬移。最后“不需要考虑超出新长度后面的元素”是在告诉你数组是定长的你只需要让前len个位置上的值都是不等于val的就行后面的残留数据面试官根本不看评测系统也不会检查。很多人做题时直接把这段话跳过了这才导致写出那种“把所有等于 val 的元素删掉然后输出新数组”的错误思路。我在实际讲题时一般会先把这三层含义说清楚因为后面所有解法的取舍都建立在这三个约束上。1.2 边界条件先列出来写代码才不会慌写这道题之前我习惯先把边界条件列成一张表写完代码后拿这些用例去套输入数组val期望返回值说明[]00空数组[1]10只有一个且等于 val[1]21只有一个但不等于 val[3,2,2,3]32常规情况[1,1,1]10全部等于 val[-3,0,-3]-31存在负数[0,1,2,2,3,0,4,2]25官方示例val 出现在中段和末尾我发现新手最容易漏掉的用例是“全部等于 val”和“空数组”这两个用例会在暴力解和首尾双指针中出现特殊行为后面我会详细展开。另一个容易漏掉的是负数很多人条件反射地写了nums[fast] 0之类的判断等于 val 的负数直接被忽略这是很可惜的扣分点。1.3 返回长度而不是返回数组为什么很多题解不用真正“删”数组在大多数语言里是定长结构nums这个变量本身没有真正的remove方法除非使用List等动态结构。题目要求的“移除”本质上是要你把不等于val的元素全部挪到数组前面并返回它们的个数。举个例子输入[1,2,3,4]val 2处理完后数组可能是[1,3,4,?]。那个?位置上的值可能是原来的 4也可能是其他残留数据这都没关系只要我返回长度 3评测就只读[1,3,4]。这个设计看似随意但非常实际在很多业务系统里数组或缓冲区的“有效长度”和“物理容量”本来就是两个概念。比如日志缓冲区的写入位置指针就相当于这里返回的新长度指针前面的数据有效后面的数据等待覆盖。理解了这一点再看双指针解法就会觉得很自然。2. 暴力解法为什么“直接删”会翻车2.1 从两层循环推导最直觉的删除逻辑我先说大多数人第一反应的做法从数组开头开始遍历一旦遇到等于val的元素就把它后面的所有元素都往前移动一位同时让数组的有效长度减一。等遍历完之后返回现在的长度。这个思路对应这段 C 代码int removeElement(vectorint nums, int val) { int n nums.size(); for (int i 0; i n; ) { if (nums[i] val) { for (int j i; j n - 1; j) { nums[j] nums[j 1]; } --n; } else { i; } } return n; }这段代码里最不直观的地方是外层循环用while而不是for。我在学习的时候一开始写成for (int i 0; i n; i)然后发现连续的相同元素漏删了这个坑会在 2.3 详细讲。总之暴力解的逻辑是正确的时间复杂度却很不理想。2.2 时间复杂度是怎么一步步变坏的最坏情况下数组里所有元素都等于val。第一次遍历发现位置 0 需要删除把后面n-1个元素全部前移第二次遍历发现位置 0 仍然是val又把后面n-2个元素前移以此类推。移动次数加起来是[ (n-1) (n-2) \dots 1 0 \frac{n(n-1)}{2} ]所以最坏时间复杂度是 O(n²)空间复杂度是 O(1)。对于题目给出的0 nums.length 100这种小范围数据暴力解在 OJ 上也能过但一旦数据量到几万甚至几十万这个效率就很危险了。而且面试官绝不会止步于“能跑”当他追问“能不能优化到 O(n)”而你答不上来时这道题就白做了。我在自己项目里也遇到过类似情况清理一个百万级的日志数组如果用“找到一条删一条、后面的往前挪”的写法处理一次要等好几秒。后来改成双指针一次遍历耗时直接降到几十毫秒。这就是这道题在真实场景下的意义。2.3 暴力解最大的坑for 循环漏删我举个例子nums [3,3,2]val 3。如果使用for (int i 0; i n; i)的写法i0发现nums[0] 3把后面元素前移数组变成[3,2]n2。此时 i 自动加 1 变成 1nums[1] 2不等于 3跳过。循环结束返回 n2但数组前两个元素是[3,2]第一个 3 并没有被删掉结果错误。问题根源在于删除当前位置的元素后后面的元素前移到了当前下标新到来的元素还没有被检查指针却已经移到了下一位。这就是经典的“漏删”。暴力解里必须让指针停留在原地再检查一次也就是用while循环或者在for循环中找到相等元素后执行--i回退。这个细节也提醒我任何“边遍历边删除”的逻辑都不简单不只是这一道题的问题。3. 双指针解法把“删除”改写成“覆盖”3.1 核心思想你真正要做的是留下非目标元素暴力解效率低的根源在于每次遇到val都搬动一大堆无关元素。换个角度想既然题目只要求“前 len 个位置是非 val 元素”那我们可以一边扫描一边把“应该留下”的元素往前面放而不是把“应该删除”的元素往后面挪。这引出了双指针快慢指针的经典思路。我们用slow指向“下一个非 val 元素应该写入的位置”用fast遍历整个数组。当fast指向的值不等于val时就把它赋值给slow位置然后slow前进一步当fast指向的值等于val时跳过不进行任何写入。遍历结束后slow的值就是新的数组长度。这个思路的关键是把删除问题转换成保留问题。你不再关心那些等于val的元素去了哪里只关心不等于val的元素有没有被有序地放到数组前半部分。3.2 代码与逐步图解C 版本int removeElement(vectorint nums, int val) { int slow 0; for (int fast 0; fast nums.size(); fast) { if (nums[fast] ! val) { nums[slow] nums[fast]; slow; } } return slow; }Python 版本def removeElement(nums, val): slow 0 for fast in range(len(nums)): if nums[fast] ! val: nums[slow] nums[fast] slow 1 return slow以nums [3,2,2,3]val 3为例完整过程如下fastnums[fast]操作数组变化slow03等于 val跳过[3,2,2,3]012不等于 val写入 nums[0][2,2,2,3]122不等于 val写入 nums[1][2,2,2,3]233等于 val跳过[2,2,2,3]2最终返回slow 2数组前两位是[2,2]符合预期。注意数组实际上变成了[2,2,2,3]后面两个元素是残留数据但题目允许多余部分出现任意值所以正确。3.3 为什么可以放心覆盖快指针永远走在前面很多第一次接触这个解法的人都会问nums[slow] nums[fast]会不会把还没遍历到的、本来应该保留的数据弄丢答案是不会。因为fast永远大于等于slow。当slow fast时写入位置就是当前位置相当于自己赋值给自己没有副作用。当slow fast时说明slow指向的一定是已经被扫描过的区域这个区域里要么是已经写入好的非 val 元素要么是原来等于 val 但已经“作废”的旧值无论哪一种覆盖掉都不影响最终结果。这么一来一次遍历就能完成时间复杂度 O(n)空间复杂度 O(1)。而且它保持了非 val 元素的相对顺序这是暴力解和很多交换解法做不到的。如果面试追问“为什么不会覆盖未处理的数据”能把这个逻辑讲清楚印象分会明显提升。3.4 一个容易走偏的变体在遍历中调用 erase 或者 remove我在实际交流中发现不少朋友会写出这样的代码for (auto it nums.begin(); it ! nums.end(); ) { if (*it val) { it nums.erase(it); } else { it; } } return nums.size();这个写法在小数据上没问题但有两个隐患。第一erase在 vector 中删除中间元素需要搬移后续元素单次 O(n)整个循环最坏 O(n²)和暴力解没有本质区别。第二erase会让迭代器失效虽然这里重新赋值了it但复杂场景下一旦忘记赋值就会产生未定义行为。如果我们想指出 STL 的存在正确做法是使用“remove 加 erase”惯用法nums.erase(remove(nums.begin(), nums.end(), val), nums.end());remove本身并不删除元素它把不等于val的元素前移返回新的逻辑结尾迭代器erase再把多余的尾部空间缩掉。这个组合内部就是类似快慢指针的思想。面试时主动提一句“如果不在竞赛环境我可能会用 STL 的 remove_erase 惯用法”能显示你知道工程实践和算法题的区别。4. 减少元素搬运的另一种思路首尾双指针4.1 当“尽量少搬数据”成为诉求时快慢指针虽好但它有一个特点每一个不等于val的元素都可能被搬动一次。如果数组里非 val 元素非常多这个搬移量不小。题目里那句“元素的顺序可以改变”其实还给了另一种可能——我们从数组两端同时处理用右边的非 val 元素去覆盖左边的 val 元素这样每个 val 位置只被覆盖一次整体搬移次数降到最低。这种思路叫“首尾双指针”或“对撞指针”。它的出发点是我要的结果只是让数组前面是非 val 元素至于它们是从哪里搬来的、顺序有没有被打乱都不重要。因此我可以用一个left从左往右找等于 val 的位置用一个right从右往左找不等于 val 的位置然后把右边找到的值复制到左边。4.2 完整代码和几个必须注意的边界C 实现int removeElement(vectorint nums, int val) { int left 0; int right nums.size() - 1; while (left right) { if (nums[left] val) { nums[left] nums[right]; --right; } else { left; } } return left; }关键逻辑只有一条当左边等于 val 时用右边当前值覆盖左边然后右指针左移。但覆盖完之后左边这个位置上的新值仍然可能等于 val比如右边连续几个数都是 val 的情况。所以这里不能让left马上前进而是让下一次循环继续检查nums[left]直到它变成一个非 val 值才让left前进。我拿一个容易出错的例子走一遍nums [1,2,3,4,3]val 3。left0nums[0]1left1。nums[1]2left2。nums[2]3等于 val用 nums[3]4 覆盖它数组变为[1,2,4,4,3]right 变为 3。left 仍然是 2。nums[2]4不等于 valleft3。left3right3nums[3]4不等于 valleft4。left4right3条件 left right 不成立退出。返回 left4数组前 4 位是[1,2,4,4]。如果把开头改成[1,2,3,3,3]val3这种“右侧全是 val”的情况left2 时nums[2]3用 nums[4]3 覆盖自己right3left 还是 2。nums[2] 仍等于 3用 nums[3]3 覆盖right2left2。此时 left2right2nums[2]3 仍等于 val继续用 nums[2] 覆盖自己right1left2。left right退出返回 left2前两位是[1,2]。这个例子里 right 左移越过了 left但返回值依然是正确的原因在于left记录的是“连续非 val 前缀的长度”。当右指针扫过的区域已经全部是 val无法再提供非 val 元素时刚好说明前面该留下的元素数量就是left的值。4.3 和快慢指针对比什么时候用哪种我整理了一个对比表方便你在面试时快速判断维度快慢指针首尾双指针是否保持相对顺序保持不保持搬移次数每个非 val 元素都可能搬一次每个 val 位置最多覆盖一次代码复杂度低不易错中等边界多典型适用场景要求稳定顺序数据量中等数据量大、顺序无要求内存搬运敏感实际工程里“保持顺序”往往是隐式需求。比如日志数组要过滤掉 error 级别剩下的日志顺序显然不能乱这时候只能用快慢指针。但如果是清理一个无序的 ID 列表顺序无所谓首尾双指针的搬移量更小性能更好。我在面试时如果先说快慢指针一般会主动加一句“如果题目允许打乱顺序我还能用首尾指针减少元素搬移”这比面试官追问后再答要主动得多。5. 从“移除元素”看一类同骨架题目移动零、删除重复项5.1 移动零移除元素 Plus 版本LeetCode 283 题“移动零”要求把数组里所有 0 移到末尾同时保持非零元素的相对顺序。表面上看和移除元素不同实际上它就是val 0的移除元素只不过移除后要在数组后面补上等量的 0。C 解法void moveZeroes(vectorint nums) { int slow 0; for (int fast 0; fast nums.size(); fast) { if (nums[fast] ! 0) { nums[slow] nums[fast]; } } while (slow nums.size()) { nums[slow] 0; } }对比移除元素唯一的新增点在于处理完非零部分后要把[slow, size)区间的元素全部置零。如果面试官让你写移除元素你可以顺带提一句这个变体展示你对双指针模型的掌握程度。5.2 删除排序数组中的重复项同一套模板的微调LeetCode 26 题“删除排序数组中的重复项”要求去除有序数组中的重复元素返回新长度。它的双指针写法是int removeDuplicates(vectorint nums) { if (nums.empty()) return 0; int slow 0; for (int fast 1; fast nums.size(); fast) { if (nums[fast] ! nums[slow]) { slow; nums[slow] nums[fast]; } } return slow 1; }这里慢指针不再单纯指向“下一个写入位置”而是指向“最后一个保留元素的位置”只有遇到新值时才会扩展。思想仍然是“用覆盖代替删除”用一个指针维护有效序列长度另一个指针负责探路。可以说“移除元素”是这一系列题目中最基础的模板后面这些题都是在它之上改了判断条件或指针含义。5.3 真实项目中的映射日志清洗、内存压缩、数据管道很多刚刷题的人会觉得这种数组题只是面试敲门砖但我在实际项目中确实用到过类似思路。举几个真实场景第一个是日志清洗。业务系统运行时会在一个环形缓冲区里存日志如果中途要过滤掉某些敏感字段或者重复日志不能等全部收集完再处理只能在写入时就地压缩。用一个写入指针扫描原始日志流一个有效指针指向下一个可以放置日志的位置完全就是快慢指针。第二个是内存分配器中的空闲块压缩。某些嵌入式系统使用静态数组管理内存回收时要把零散的空闲块合并到尾部这本质上也是原地把有效对象搬到前段。第三个是数据库存储引擎中的记录删除。有些存储引擎删除记录后不会立即物理清除而是把页内后面的记录往前覆盖同时更新逻辑长度。这几乎就是这道题的工业版。所以“移除元素”不只是一道为了面试准备的题目它背后是一整套“原地过滤、延迟清理”的工程思想。6. 面试现场怎么讲这道题才能拿高分6.1 拿到题目先确认前提面试时最忌讳拿到题目就写。我会先花 30 秒确认三个问题第一数组能不能被覆盖或交换第二返回值是长度还是数组本身第三要不要保持非目标元素的相对顺序。这三个问题的答案直接决定解法选型。如果面试官说“保持顺序”那就快慢指针如果说“顺序随意”你可以做快慢指针也可以做首尾双指针这时候主动二选一并且说明理由比闷头写强很多。6.2 递进式的讲解节奏我推荐的讲解顺序先说暴力解明确它的复杂度是 O(n²)然后指出“删除是昂贵的操作但我们可以把删除变成覆盖”再引出快慢指针写出 O(n) 代码如果发现面试官对性能敏感再补充首尾双指针。这个递进过程本身就是在展示你的算法思维路径而不是直接跳到最后答案。面试官要看到的不是你背下了最优解而是你能从朴素方案出发一步步分析出更优方案。6.3 高频追问和参考回答这道题面试官特别爱追问几个点。一个是“为什么不能用 erase”此时你可以解释 vector 的 erase 删除中间元素需要搬移所有后续元素每次 O(n)多次调用累计 O(n²)空间上虽然 O(1)但时间上不及双指针。另一个是“返回长度之后数组后面的元素需要清理吗”答案是不需要题目明确说了超出新长度的部分可以被忽略这也是很多工程系统“逻辑长度”与“物理容量”分离的体现。还有“听起来简单你能不能解释为什么快指针遇到 val 时可以不写”因为不等于 val 的元素才会被往前放置等于 val 的直接跳过相当于它被过滤掉了留下来的位置会被后续的非 val 元素覆盖。6.4 最终代码模板与自测用例给出我目前最常用的两个模板。C 快慢指针int removeElement(vectorint nums, int val) { int slow 0; for (int fast 0; fast nums.size(); fast) { if (nums[fast] ! val) { nums[slow] nums[fast]; } } return slow; }Python 快慢指针def removeElement(nums, val): slow 0 for fast in range(len(nums)): if nums[fast] ! val: nums[slow] nums[fast] slow 1 return slow写完代码后我建议至少自测四个用例空数组、数组全部等于 val、数组没有 val、val 连续出现在开头和末尾各一次。把这些用例想清楚代码基本不会错。这道题我前后反复写过很多次最大的体会是不要把它当成“删除题”而是当成“搬运题”。你的目标不是抹掉那些等于 val 的元素而是把不该留下的元素过滤掉、把该留下的元素整齐地放到前面。一旦视角从删除切换到覆盖下标问题、漏删问题、复杂度问题全都会顺下来。最后再分享一个实际经验面试时如果你能主动画出 slow 和 fast 的移动过程比单纯报出答案要更能打动面试官。很多基础题到最后拼的不只是代码而是你能不能把背后的“为什么”讲得足够清楚。