LeetCode 27 · 移除元素——双指针一次遍历搞定，O(n²) 暴力解瞬间不香了

题目速览给你一个数组nums和一个值val要求原地移除所有等于val的元素返回移除后数组的新长度。不能使用额外空间必须用 O(1) 的额外内存原地修改输入数组。先搞清楚一件事数组能删除吗不能。数组在内存中是连续存储的你没办法在物理层面真正删除某个元素——所谓删除本质上是用后面的元素覆盖前面的元素。这也是Array.splice()/ Cerase()这类库函数慢的根本原因删一个元素后面所有元素都要向前移动一位时间复杂度 O(n)如果在循环里反复调用就变成了 O(n²)。关于库函数的使用原则刷算法题时有一条实用准则情况建议库函数直接就能解决该题的核心逻辑❌ 不推荐用失去练习意义库函数只是解题的某个小步骤✅ 推荐用专注核心逻辑本题核心就是移除元素直接用splice/filter一行搞定但什么都没学到——所以我们手写。方法一暴力解 O(n²)思路两层 for 循环外层遍历找到等于val的元素内层让后面所有元素向前移一位。functionremoveElement(nums,val){letsizenums.length;for(leti0;isize;i){if(nums[i]val){// 找到目标值后面所有元素前移for(letji1;jsize;j){nums[j-1]nums[j];}i--;// 前移后当前位置需要重新检查size--;// 有效长度减一}}returnsize;}缺点两层循环时间复杂度 O(n²)数据量大时性能差。方法二双指针快慢指针O(n) ✅ 推荐核心思想用两个指针在同一个数组上协作一次遍历完成任务。指针职责fast快指针遍历原数组寻找不等于val的元素slow慢指针维护新数组的写入位置slow的值就是新数组的长度执行过程fast每次向前走一步当nums[fast] ! val时把这个有效元素写入nums[slow]然后slow当nums[fast] val时fast继续走slow不动相当于跳过了这个值functionremoveElement(nums,val){letslow0;for(letfast0;fastnums.length;fast){if(nums[fast]!val){// ! 是严格不等同时比较值和类型nums[slow]nums[fast];slow;}}returnslow;// slow 就是新数组的长度}以nums [3,2,2,3]val 3为例走一遍初始slow0, fast0 fast0: nums[0]3 val跳过 fast1: nums[1]2 ! valnums[0]2slow1 fast2: nums[2]2 ! valnums[1]2slow2 fast3: nums[3]3 val跳过 结果nums[2,2,2,3]返回 slow2前两位有效复杂度对比方法时间复杂度空间复杂度暴力两层循环O(n²)O(1)快慢双指针O(n)O(1)总结双指针快慢指针是处理数组原地操作的经典范式本题是它最基础的应用场景。记住这个模板fast 负责探路slow 负责落笔。fast 扫到有效值就交给 slow 写入slow 的最终位置就是答案。