LeetCode 27 移除元素：从暴力解法到双指针的思维跃迁，一篇讲透原地删除的核心本质

作者：新兰2026.11.07 02:20浏览量：0

简介：本文以LeetCode 27「移除元素」为切入点，深入剖析数组原地删除问题的本质。文章从暴力解法的性能瓶颈出发，系统讲解快慢双指针与首尾交换法两种最优解，并通过循环不变式、读写分离等底层逻辑，揭示双指针技术的通用性。同时提供11条避坑清单、7个高频追问话术及4道同模板变体题解析，帮助读者建立真正的边界意识与算法思维，从容应对面试中的追问与拓展。

一、为什么一道“简单题”能问倒人？

在算法面试中，LeetCode 27“移除元素”常被视作入门级题目。但正因其简单，反而成为面试官深挖细节的最佳切入点。许多候选人能轻松写出两层 for 循环的暴力解法，却对时间复杂度、数据迁移代价、原地修改的含义缺乏深刻理解。当面试官追问“若数组长度达到百万级，你的解法还能接受吗？”时，不少人会陷入沉默。

这道题的迷人之处于此：它表面上只要求“删除值为 val 的元素”，实则考察的是对数组存储模型的理解——数组的删除并非真正“移除”内存单元，而是逻辑上的覆盖。理解这一层，才算真正拿到双指针技术的钥匙。

二、暴力解法：直观但代价高昂

第一次接触这道题，最直接的思路是：遍历数组，每当遇到等于 val 的元素，就用它后面的所有元素依次前移一位覆盖当前位置，同时缩短有效长度。

  1. public int removeElement(int[] nums, int val) {
  2.     int n = nums.length;
  3.     for (int i = 0; i < n; ) {
  4.         if (nums[i] == val) {
  5.             for (int j = i; j < n - 1; j++) {
  6.                 nums[j] = nums[j + 1];
  7.             }
  8.             n--;
  9.             // 注意：此处不执行 i++，因为新移到 i 位置的元素需要重新检查
  10.         } else {
  11.             i++;
  12.         }
  13.     }
  14.     return n;
  15. }

这段代码虽然能通过测试，但时间复杂度为 O(n²)：当数组中大量元素需要被移除时，内层迁移操作会频繁发生。假设数组长度为 100 万，其中 50 万是待删值，则总迁移次数接近 2.5 亿次，性能瓶颈显而易见。面试官问“数据量大了怎么办”，正是希望候选人跳出这种“物理模拟”思维。

三、双指针的思想起点：读写分离

理解双指针的首要前提，在于明确读与写的职责分离。我们可以想象有两个人同时操作数组：

  • 读指针（通常命名为 i）：负责遍历整个数组，逐项检查元素是否等于 val，它不关心写操作进行到哪里。
  • 写指针（通常命名为 slow）：负责记录下一个可写入的位置，它指向的位置永远是“当前已处理区域与待处理区域的分界线”。

这个视角的转变至关重要。暴力解法中，每一次删除都要进行一轮全量迁移，本质上是把读和写混为一谈——删除操作本身既是判断也是物理移动。而双指针则将“判断”与“覆盖”解耦：读指针只管往前扫，遇到非目标值就交给写指针落位，遇到目标值就忽略它。

四、快慢双指针：保序与高效兼备的解决方案

4.1 核心实现与循环不变式

快慢双指针的代码极其简洁：

  1. public int removeElement(int[] nums, int val) {
  2.     int slow = 0;
  3.     for (int fast = 0; fast < nums.length; fast++) {
  4.         if (nums[fast] != val) {
  5.             nums[slow++] = nums[fast];
  6.         }
  7.     }
  8.     return slow;
  9. }

理解这段代码的关键在于建立循环不变式：在任意时刻，[0, slow) 区间内的所有元素都是不包含 val 的、保留在原数组前部的有效元素；而 [fast, nums.length) 区间是尚未遍历的部分；[slow, fast) 区间则是已经被跳过或覆盖的中间地带。

循环不变式还回答了面试中最常见的追问：为什么返回 slow 而不是 slow + 1？ 因为 slow 自身就是一个计数器，每写入一个保留元素它就递增一次。最终 slow 的值恰好等于保留元素的数量，而由于数组索引从 0 开始，slow 也恰好指向下一个可写位置。这里的边界处理是自然而然的，并不需要额外调整。

4.2 自赋值是否安全？

当 fast 指向的元素与 slow 指向的位置相同时，执行 nums[slow] = nums[fast] 既有自赋值操作。很多读者担心这会造成问题，但事实上完全安全——因为赋值前后值相等，相当于对数组无扰动。更严谨地说，复制操作本身就是恒等变换，不引发任何副作用。

不过自赋值在极端场景下可能造成轻微的 CPU 缓存压力，但这在算法层面可以忽略不计。面试中提及这一点反而能让面试官看到你对底层实现的感知。

五、首尾交换法：不保序时的极致优化

如果对“移除后相对顺序保持不变”没有硬性要求，我们可以采用另一种策略——首尾交换法。其核心思想在“填坑”而非“覆盖”：

  • 维护头指针 left 和尾指针 right，初始时分别指向数组两端。
  • 当 nums[left] == val 时，直接用 nums[right] 的值填在 left 位置，同时向左移动 right。
  • 如果 nums[left] != val，则向右移动 left。
  • 当 left > right 时结束循环，有效长度即为 left。
  1. public int removeElement(int[] nums, int val) {
  2.     int left = 0;
  3.     int right = nums.length - 1;
  4.     while (left <= right) {
  5.         if (nums[left] == val) {
  6.             nums[left] = nums[right];
  7.             right--;
  8.             // 注意：此处 left 不递增
  9.         } else {
  10.             left++;
  11.         }
  12.     }
  13.     return left;
  14. }

5.1 为什么覆盖后 left 不能立即递增？

这是该方法最容易被忽略的边界陷阱。当我们用 nums[right] 覆盖 nums[left] 后，从右端搬来的这个元素本身可能也等于 val。因此我们需要在下一轮循环中重新检查 left 位置的新值。如果贸然执行 left++，就会放过一个应当被移除的元素。

5.2 开区间还是闭区间？

在循环条件的写法上，存在 left <= right（闭区间）和 left < right（开区间）两种习惯。闭区间意味着 left 和 right 所指位置都是尚未处理的；开区间则保证二者之间至少有一个空位。对于本题，闭区间写法更为直观，但在判断循环终止时需格外小心——一旦 left 越过 right，说明所有有效元素已被正确放置在 [0, left) 区间内。

六、两种方案的选择策略：一张表说清楚

场景特征 推荐方案 时间复杂度 赋值次数
要求保留原顺序 快慢双指针 O(n) n - k（k为保留元素数量）
不要求顺序 & val 出现稀疏 首尾交换法 O(n) k（k为待删除元素数量）
不要求顺序 & val 出现频繁 首尾交换法 O(n) n - k

赋值次数差异的实质在于：快慢指针在遍历过程中会将每一个保留元素复制一遍（即使不需要移动），而首尾交换法跳过所有不需要移动的位置，只有当发现目标值时才进行覆盖。对比之下，若数组中待删除的值非常少，首尾交换的代价极小；而待删除值较多时，快慢指针的迁移成本可忽略不计，但首尾交换每次覆盖后还需重新检查，整体依然高效。

面试官的潜在期望：你是否能根据题目附加条件（是否保留相对顺序、val 的分布特征）灵活选型，而不是机械套用模板。

七、11条避坑清单

  1. 快慢指针中，写指针只移动一次——每次覆盖后立即自增，不要额外操作。
  2. 读指针必须遍历到数组末尾，不能因提前看到有效元素而中断。
  3. 首尾交换法中，覆盖后不要立即移动 left，必须留待下一轮检查。
  4. 首尾交换法的循环条件建议使用 left <= right，并仔细推演终止状态。
  5. 返回长度必须与实际有效元素数量一致，不能误用 nums.length。
  6. 当数组长度为 0 时，应直接返回 0，避免数组越界。
  7. 当数组所有元素都等于 val 时，快慢指针返回 0，首尾交换返回 0，两者行为一致。
  8. 当数组没有待删元素时，快慢指针自赋值多次，但不应影响结果。
  9. 务必区分“有效长度”与“数组物理长度”——后者保持不变。
  10. 如果面试官要求统计被删除的元素数量，则用物理长度减去返回长度即可。
  11. 代码中不要出现魔法数字，使用常数 val 参数传递即可。

八、面试高频追问与话术

  • Q1：为什么返回 slow 而不是 slow + 1？
    A：slow 本身记录已保留元素个数，数组索引以 0 为基准，因此 slow 同时是长度与下一个可写位置。

  • Q2：自赋值什么时候会发生？安全吗？
    A：当 fast == slow 且 nums[fast] != val 时发生。此操作是恒等赋值，不影响数组内容。

  • Q3：ArrayList 的 removeIf 方法是怎么做的？
    A：ArrayList 内部采用类似快慢指针的思想，先遍历标记需要保留或删除的元素，然后在一次遍历中完成批量迁移，避免了多次单点删除导致的频繁数组拷贝。

  • Q4：Java Stream 能解决这个问题吗？
    A：Arrays.stream(nums).filter(x -> x != val).toArray() 确实能完成任务，但它开辟了新的数组空间，不满足“原地修改”的要求，空间复杂度为 O(n)，因此不是合格解。

  • Q5：时间复杂度和空间复杂度各是多少？
    A：快慢指针与首尾交换均为 O(n) 时间、O(1) 空间，但赋值次数不同，需结合场景区分。

  • Q6：如果允许额外数组，这道题还能怎么解？
    A：可以遍历原数组并将非目标值写入新数组，但空间复杂度升至 O(n)。面试官通常希望看到你主动提出空间优化方案。

  • Q7：这道题的变体会怎么考？
    A：常见变体包括“删除有序数组中的重复项”（LeetCode 26）、“移动零”（LeetCode 283）、“删除有序数组中的重复项 II”（LeetCode 80）和“比较含退格的字符串”（LeetCode 844）。这些题目的核心骨架与双指针一致，稍作调整即可套用。

九、同一套骨架，四道变体题的贯通

  • LeetCode 26（删除有序数组中的重复项）：快慢指针的变体，保留条件从“!= val”变为“与前一元素不同”。
  • LeetCode 283（移动零）：把“val”具像化为“0”，保留条件为“!= 0”，注意最后补零操作。
  • LeetCode 80（删除有序数组中的重复项 II）：允许最多保留两个相同元素，只需额外维护一个计数器或与 slow - 2 位置比较。
  • LeetCode 844（比较含退格的字符串）：本质是双指针从后向前扫描，处理退格符号时回退写指针。

掌握双指针的读写分离思想，这些变体便不再需要逐一背诵，而是同一套逻辑的自然延伸。

十、结语：从题目本身到思维模式

LeetCode 27的价值远不止一道“简单题”。它训练的是工程师在有限资源下处理数据迁移的底层思维：如何减少赋值次数、如何保证边界正确、如何在约束条件下取舍方案。下一次面对数组类问题时，建议先问自己三个问题：是否需要保序？val 分布如何？能否接受 O(1) 额外空间？想清楚这些，再落笔写代码，你的解题思路自然会比流水线式背题高明许多。

最热文章