---

雙指針法高效解決「移除元素」問題

一、問題描述

給定一個整數數組 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. 指針移動：
   • 只有確認當前元素不是目標值時才移動左指針
   • 每次覆蓋操作后右指針必定左移

四、復雜度分析

指標	值	說明
時間復雜度	O(n)	最多遍歷數組一次
空間復雜度	O(1)	只使用了常數級別的額外空間

五、與其他解法的比較

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. 需要熟練掌握指針邊界條件的控制