LeetCode 27 · 移除元素——双指针一次遍历搞定，O(n²) 暴力解瞬间不香了
题目速览
给你一个数组nums和一个值val，要求原地移除所有等于val的元素，返回移除后数组的新长度。
不能使用额外空间，必须用 O(1) 的额外内存原地修改输入数组。
先搞清楚一件事：数组能"删除"吗？
不能。数组在内存中是连续存储的，你没办法在物理层面真正删除某个元素——所谓"删除"，本质上是用后面的元素覆盖前面的元素。
这也是Array.splice()/ C++erase()这类库函数"慢"的根本原因：删一个元素，后面所有元素都要向前移动一位，时间复杂度 O(n)；如果在循环里反复调用，就变成了 O(n²)。
关于库函数的使用原则
刷算法题时有一条实用准则：
| 情况 | 建议 |
|---|---|
| 库函数直接就能解决该题的核心逻辑 | ❌ 不推荐用（失去练习意义） |
| 库函数只是解题的某个小步骤 | ✅ 推荐用（专注核心逻辑） |
本题核心就是"移除元素"，直接用splice/filter一行搞定但什么都没学到——所以我们手写。
方法一：暴力解 O(n²)
思路：两层 for 循环，外层遍历找到等于val的元素，内层让后面所有元素向前移一位。
functionremoveElement(nums,val){letsize=nums.length;for(leti=0;i<size;i++){if(nums[i]===val){// 找到目标值，后面所有元素前移for(letj=i+1;j<size;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){letslow=0;for(letfast=0;fast<nums.length;fast++){if(nums[fast]!==val){// !== 是严格不等，同时比较值和类型nums[slow]=nums[fast];slow++;}}returnslow;// slow 就是新数组的长度}以nums = [3,2,2,3]，val = 3为例走一遍：
初始：slow=0, fast=0 fast=0: nums[0]=3 === val，跳过 fast=1: nums[1]=2 !== val，nums[0]=2，slow=1 fast=2: nums[2]=2 !== val，nums[1]=2，slow=2 fast=3: nums[3]=3 === val，跳过 结果：nums=[2,2,2,3]，返回 slow=2（前两位有效）复杂度对比
| 方法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 暴力两层循环 | O(n²) | O(1) |
| 快慢双指针 | O(n) | O(1) |
总结
双指针（快慢指针）是处理数组原地操作的经典范式，本题是它最基础的应用场景。记住这个模板：
fast 负责探路，slow 负责落笔。fast 扫到"有效值"就交给 slow 写入，slow 的最终位置就是答案。