当前位置：首页 > news >正文

双指针专题(一)：其实是“覆盖”元素——「移除元素」

news 2026/3/26 22:25:55

欢迎来到双指针专题第一篇！

场景想象：你手里有一叠扑克牌（数组），里面混进去了几张“鬼牌”（需要移除的元素val）。

暴力做法：每看到一张鬼牌，把它抽出来，然后把后面所有的牌往前挪一格填补空缺。
双指针做法：如果不想要鬼牌，我们根本不用“抽”它。我们只需要把好牌一张张地往前挪，把鬼牌的位置给覆盖掉就行了。

力扣 27. 移除元素

https://leetcode.cn/problems/remove-element/

题目分析：

输入：数组nums，值val。
目标：原地移除所有数值等于val的元素。
输出：返回移除后数组的新长度k。
要求：空间复杂度必须是 O(1)。

例子：nums = [3, 2, 2, 3], val = 3

结果：k = 2,nums的前两个元素应该是[2, 2]。后面剩啥无所谓。

核心思维：快慢指针 (Fast & Slow Pointers)

我们定义两个指针：

快指针 (fast)：探路者。它的任务是遍历数组，寻找新数组里需要的元素（即不等于val的元素）。
慢指针 (slow)：建筑师。它指向下一个新元素应该存放的位置。

操作逻辑：

fast指针在前面跑，如果nums[fast]是“鬼牌”（等于val）：
- fast继续往前跑，忽略它（相当于直接跳过）。
如果nums[fast]是“好牌”（不等于val）：
- 把这张好牌拿过来，覆盖到slow指向的位置：nums[slow] = nums[fast]。
- 然后slow向前走一步，准备接下一张好牌。
最后，slow的数值就是新数组的长度。

为什么不用`splice`？

作为前端，我们太熟悉nums.splice(i, 1)了。但是，splice的底层实现是把删除位置后面的所有元素都往前挪一位。这是一个 O(N) 的操作。如果你在for循环里用splice，那就是 O(N2) 的复杂度。而双指针法只需要遍历一次，复杂度是O(N)。

代码实现 (JavaScript)

JavaScript

/** * @param {number[]} nums * @param {number} val * @return {number} */ 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++; } // 如果 nums[fast] === val，那就什么都不做 // 快指针会自动 fast++ 跳过它，慢指针原地不动 } // 此时 slow 的值，刚好就是新数组的长度 return slow; };