双指针法高效解决「移除元素」问题

双指针法高效解决「移除元素」问题

一、问题描述

给定一个整数数组 nums 和一个整数 val，我们需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。要求：

• 必须原地修改输入数组
• 不需要考虑数组中超出新长度后面的元素
• 空间复杂度应为 O(1)

二、解法解析：双指针法

1. 核心思想

采用首尾双指针策略：

• left 指针从数组头部开始，负责构建新数组
• right 指针从数组尾部开始，提供替换元素

2. 算法步骤

public int removeElement(int[] nums, int val) {
    int left = 0, right = nums.length - 1;  // 初始化双指针
    while (left <= right) {  // 循环条件
        if (nums[left] == val) {  // 发现目标值
            nums[left] = nums[right];  // 用末尾元素覆盖
            right--;  // 右指针左移
        } else {
            left++;  // 非目标值，左指针右移
        }
    }
    return left;  // left即为新长度
}

3. 执行过程示例

以 nums = [3,2,2,3], val = 3 为例：

1. 初始状态：[3,2,2,3], left=0, right=3
2. nums[0]==3 → 替换为nums[3] → [3,2,2,3], right=2
3. nums[0]==3 → 替换为nums[2] → [2,2,2,3], right=1
4. nums[0]==2 → left=1
5. nums[1]==2 → left=2
6. left>right 循环结束
7. 返回 left=2，新数组为 [2,2,...]

三、关键点分析

1. 边界条件：while (left <= right) 确保处理所有元素
2. 元素交换：发现目标值时直接覆盖而非交换，减少操作
3. 指针移动：
   • 只有确认当前元素不是目标值时才移动左指针
   • 每次覆盖操作后右指针必定左移

四、复杂度分析

五、与其他解法的比较

1. 快慢指针法

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

• 更适合目标值较少的情况
• 元素移动次数可能更多

2. 本解法的优势

• 在目标值较多时效率更高
• 每个目标值只需一次赋值操作
• 保留了数组末端的原有元素

六、实际应用场景

这种双指针技巧适用于：

1. 需要原地修改数组的问题
2. 需要保持部分元素顺序的问题
3. 资源受限环境下的数组操作

七、总结

这种首尾双指针解法：

1. 是处理数组原地修改的高效方法
2. 通过巧妙地指针移动减少不必要的操作
3. 体现了算法设计中空间换时间的思想
4. 需要熟练掌握指针边界条件的控制