【LeetCode：27 移除元素】双指针快速掌握移除题 (附五道题)

超级苦力怕

发布于 2025-12-24 09:00:03

950

前置知识：拥有一门语言基础与数组基础

1. 移除元素：原理、模板与经典题解

一句话：通过双指针法，一个快指针去一直寻找新元素，一个慢指针更新新数组。

使用前提：

示例：

假设数组 nums = [3, 2, 2, 3, 5]，要移除的元素 val = 3。

指针定义：
- 慢指针 slow：指向 “已处理的有效数组的末尾”（即最终保留元素的位置）。
- 快指针 fast：遍历整个数组，负责 “寻找需要保留的元素”。
执行过程：
1. 初始时 slow = 0，fast = 0。
2. fast 移动到索引 0：nums[0] = 3（等于 val，需移除），slow 不动，fast 继续后移（fast = 1）。
3. fast 移动到索引 1：nums[1] = 2（不等于 val，需保留），将 nums[fast] 赋值给 nums[slow]（数组不变），slow 后移（slow = 1），fast 继续后移（fast = 2）。
4. fast 移动到索引 2：nums[2] = 2（需保留），赋值给 nums[slow]（数组不变），slow = 2，fast = 3。
5. fast 移动到索引 3：nums[3] = 3（需移除），slow 不动，fast 后移（fast = 4）。
6. fast 移动到索引 4：nums[4] = 5（需保留），赋值给 nums[slow]（数组变为 [2, 2, 5, 3, 5]），slow = 3，fast 结束遍历。

思路：快指针负责 “筛选” 有效元素（不等于 val 的元素），慢指针负责 “记录” 有效元素的位置。当快指针找到有效元素时，就把它 “搬运” 到慢指针的位置，然后慢指针前进一格。最终，slow 的值就是移除元素后新数组的长度，数组前 slow 个元素即为保留的有效元素。

2. 统一模板速查

小结（何时用哪种）：

快慢指针（稳定保序）：用于“按条件筛选保留元素”，不关心被移除部分；保留相对顺序。
相向双指针（原地分区，可能不保序）：用于“快速剔除/分区”，不要求原顺序，写法更简。

不变量与模板：

快慢指针不变量：[0, slow) 始终为“已构建的有效区间”；[fast, n) 为“未处理区间”。
相向双指针不变量：[0, left) 为有效区间尾；(right, n-1] 为“已丢弃（或放置到尾部）”区间。

// 模板 A：快慢指针（稳定保序，过滤保留）
int compact(int[] nums, java.util.function.IntPredicate keep) {
    int slow = 0;
    for (int fast = 0; fast < nums.length; fast++) {
        if (keep.test(nums[fast])) {
            nums[slow++] = nums[fast];
        }
    }
    return slow; // 新长度；前 slow 个元素有效
}

// 模板 B：相向双指针（原地分区，可能不保序）
int partitionRemove(int[] nums, java.util.function.IntPredicate remove) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        if (remove.test(nums[left])) {
            nums[left] = nums[right];
            right--;
        } else {
            left++;
        }
    }
    return left; // 新长度；[0, left) 为有效区间
}

示例(快慢指针)：

当寻找到需要移除的元素时，慢指针不动，即让快指针跳过该元素，达到后面的元素统一往前移一格(覆盖)

class Solution {
    public int removeElement(int[] nums, int val) {
        // 快慢指针
        int slow = 0;
        //快指针负责在数组遍历，寻找新元素
        for (int fast = 0; fast < nums.length; fast++) {
            //当没遍历到移除元素时
            if (nums[fast] != val) {
                //慢指针自动覆盖数组(寻找的元素)
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
}

示例(相向双指针法):

left 代表新数组的长度；当把 nums[left] 替换为 nums[right] 并 right-- 时，相当于“剔除”了一个元素到尾部区域（不保序）。

// 相向双指针法
class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            //这里可以理解为把移除的元素放在后面，由于不需要考虑新数组外的数组，所以直接移除
            if(nums[left] == val){
                nums[left] = nums[right];
                right--;
            }else {
                // 这里兼容了right指针指向的值与val相等的情况
                left++;
            }
        }
        return left;
    }
}

3. LeetCode 相关习题讲解

27：移除元素（简单）

题目简介

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。

用户评测：

评测机将使用以下代码测试您的解决方案：

int[] nums = [...]; // 输入数组
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 长度正确的预期答案。
                            // 它以不等于 val 的值排序。

int k = removeElement(nums, val); // 调用你的实现

assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有的断言都通过，你的解决方案将会通过。

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

提示：

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

思路

使用快慢指针和相向双指针都可，因为只要移除元素，所以直接套用即可。

(1) 快慢指针

class Solution {
    public int removeElement(int[] nums, int val) {
        int slow=0;
        for(int fast=0;fast<nums.length;fast++){
            if(nums[fast]!=val){
                nums[slow]=nums[fast];
                slow++;
            }
        }
        return slow;
    }
}

(2) 相向双指针

class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            if(nums[left] == val){
                nums[left] = nums[right];
                right--;
            }else {
                left++;
            }
        }
        return left;
    }
}

26：删除有序数组中的重复项（简单）

题目简介

给你一个 非严格递增排列 的数组 nums ，请你原地删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持一致。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k。去重后，返回唯一元素的数量 k。

nums 的前 k 个元素应包含 排序后 的唯一数字。下标 k - 1 之后的剩余元素可以忽略。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有断言都通过，那么您的题解将被通过。

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4,_,_,_,_,_]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

1 <= nums.length <= 3 * 104
-100 <= nums[i] <= 100
nums 已按 非递减 顺序排列。

思路：快慢指针

使用快慢指针，原理和移除单个元素相同，可以通过慢指针指向元素是否与快指针指向元素相同，进行移除。

class Solution {
    public int removeDuplicates(int[] nums) {
        int slow=0;
        for(int fast=0;fast<nums.length;fast++){
            if(nums[fast]!=nums[slow]){
                nums[++slow]=nums[fast];
            }
        }
        return slow+1;
    }
}

283：移动零（简单）

题目简介

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

提示:

1 <= nums.length <= 10^4
-2^31 <= nums[i] <= 2^31 - 1

**进阶：**你能尽量减少完成的操作次数吗？

思路

(1) 快慢指针：两次遍历

可以将任务拆分为“移除所有 0”和“将 0 填到最后”，进行两次遍历。

class Solution {
    // 移除所有 0，再补零到末尾
    public void moveZeroes(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        // 将 0 填到最后
        for (int i = slow; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

(2) 原地分区：一次遍历

借鉴分区思想：维护 [0, slow) 为非零区域，[slow, fast] 为扫描区域，遇到非零则交换到前部。

以 0 作为“分界”，将非 0 元素放置左边即可：

class Solution {
    public void moveZeroes(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                int temp = nums[fast];
                nums[fast] = nums[slow];
                nums[slow++] = temp;
            }
        }
    }
}

844：比较含退格的字符串（简单）

题目简介

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

**注意：**如果对空文本输入退格字符，文本继续为空。

示例 1：

输入：s = "ab#c", t = "ad#c"
输出：true
解释：s 和 t 都会变成 "ac"。

示例 2：

输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 ""。

示例 3：

输入：s = "a#c", t = "b"
输出：false
解释：s 会变成 "c"，但 t 仍然是 "b"。

提示：

1 <= s.length, t.length <= 200
s 和 t 只含有小写字母以及字符 '#'

进阶：

你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？

思路

(1) 快慢指针

通过将字符串转为数组，就可以将单个字符串转化为移除元素的问题了，不同的是遇到#要回退一格，返回的新数组由慢指针决定长度

缺点是空间复杂度是O(n)，不满足题目的进阶

class Solution {
    public boolean backspaceCompare(String s, String t) {
        //判断字符串是否相等
        return getString(s).equals(getString(t));
    }

    public static String getString(String str){
        char[] x = str.toCharArray();
        int slow=0;
        for(int fast=0; fast < x.length; fast++){
            if(x[fast] != '#'){
                x[slow++] = x[fast];
            }else if(x[fast] == '#' && slow!=0){
                //这里一定要标注slow!=0,测试用例有的字符第一个就是#
                slow--;
            }
        }
        return String.valueOf(x,0,slow);
    }
}

(2) 双指针

通过从后往前遍历字符串，在循环如果遇到#,再次向前一格，最后对比即可

class Solution {
    public boolean backspaceCompare(String S, String T) {
        int i = S.length() - 1, j = T.length() - 1;
        int skipS = 0, skipT = 0;  //代表着是否需要跳过，也可以代表#的个数

        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                //当是#或上一个元素是#时候，向前一格
                if (S.charAt(i) == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }
            while (j >= 0) {
                if (T.charAt(j) == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }
            if (i >= 0 && j >= 0) {
                if (S.charAt(i) != T.charAt(j)) {
                    return false;
                }
            } else {
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }
            i--;
            j--;
        }
        return true;
    }
}

977：有序数组的平方（简单）

题目简介

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 已按 非递减顺序 排序

思路：相向双指针

由于按照非递减顺序排序，所以是有规律的，在负数部分，最左边的平方是最大的，在正数部分，最右边的平方是最大的。因此，我们可以从两边向中间合并。这样不仅不需要计算从哪里开始，也包含了全正数和全负数的情况。

构建新的数组，让左右两边平方的最大值放在末尾，往前一格，重复上述动作

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        int left = 0;
        int right = n - 1;
        for (int i = n - 1; i >= 0; i--) {
            int x = nums[left] * nums[left];
            int y = nums[right] * nums[right];
            if (x > y) {
                ans[i] = x;
                left++;
            } else {
                ans[i] = y;
                right--;
            }
        }
        return ans;
    }
}