雙指針方法是解決數組或鏈表問題中非常高效的技巧之一，尤其適用于原地修改數組或減少時間復雜度的場景。以下是對雙指針方法的詳細講解。

1. 雙指針方法的核心思想

雙指針方法通常使用兩個指針（或索引）在數組或鏈表中協同工作，通過一次遍歷完成任務。常見的雙指針模式包括：

• 快慢指針：一個指針用于遍歷（快指針），另一個指針用于標記目標位置（慢指針）。
• 左右指針：一個指針從頭部開始，另一個從尾部開始，向中間移動。

在?RemoveElement?問題中，使用的是快慢指針。

2. 問題描述

給定一個數組?nums?和一個值?val?，需要原地移除所有等于?val?的元素，并返回新數組的長度。要求：

• 空間復雜度為?O(1)?（不能使用額外數組）。
• 不需要考慮新數組長度之后的元素。

3. 雙指針實現步驟

(1) 初始化指針

• 慢指針?index?：指向下一個有效元素的存儲位置（初始為?0?）。
• 快指針?i?：用于遍歷數組（初始為?0?）。

(2) 遍歷數組

• 快指針?i?從?0?開始，逐個檢查數組元素。
• 如果?nums[i] != val?，說明這是一個需要保留的元素：
  • 將其賦值給?nums[index]?。
  • 慢指針?index?右移一位。
• 如果?nums[i] == val?，直接跳過（快指針繼續右移）。

(3) 終止條件

• 快指針?i?遍歷完整個數組后，慢指針?index?的值即為新數組的長度。

4. 代碼實現

public int RemoveElement(int[] nums, int val)
{int index = 0; // 慢指針for (int i = 0; i < nums.Length; i++) // 快指針 i{if (nums[i] != val){nums[index] = nums[i]; // 保留該元素index++; // 慢指針右移}}return index; // 新數組長度
}

5. 示例分析

以?nums = [3, 2, 2, 3]?，?val = 3?為例：

最終返回?index = 2?，新數組為?[2, 2, ...]?（后續元素無需關心）。

6. 復雜度分析

• 時間復雜度：?O(n)?，只需遍歷一次數組。
• 空間復雜度：?O(1)?，僅使用常數級別的額外空間。

7. 雙指針的適用場景

1. 原地修改數組：如刪除重復項、移除特定元素。
2. 鏈表問題：如判斷環形鏈表、找到中間節點。
3. 有序數組：如兩數之和、合并有序數組。

8. 總結

雙指針方法是解決數組/鏈表問題的利器，核心在于：

• 明確指針的分工（快指針遍歷，慢指針標記）。
• 注意邊界條件（如空數組、全部元素需刪除）。
• 靈活選擇變體（如交換法優化）。