題目描述:給定一個整數陣列 nums 和一個整數 val,請**原地(in-place)**移除所有值等於 val 的元素,並回傳移除後陣列的新長度。不需要考慮新長度之外的元素,空間複雜度必須為 O(1)。
解題思路:使用**雙指針(Two Pointers)**法。維護一個「寫入指針」k,代表下一個可寫入位置的索引,初始為 0。遍歷陣列時,若當前元素 nums[i] 不等於 val,就將它寫到 nums[k] 並將 k 加一;若等於 val 則直接跳過。遍歷結束後,k 即為新陣列的長度。這樣做的關鍵在於:所有不等於 val 的元素都被緊密地寫在陣列前端,且只需一次線性掃描即可完成。
時間複雜度:O(n) — 只需一次線性掃描整個陣列,n 為陣列長度。
空間複雜度:O(1) — 僅使用常數個額外指針變數,原地修改陣列,不需額外空間。
1. Initialize write pointer k = 0
2. For each index i from 0 to len(nums) - 1:
a. If nums[i] != val:
- Write nums[i] into nums[k]
- Increment k
3. Return k as the new length方法一:雙指針(頭尾對向) 使用左右兩個指針,左指針從頭找等於 val 的元素,右指針從尾找不等於 val 的元素,互換後左指針右移、右指針左移,直到兩指針相遇。此法在 val 出現次數很少時特別高效,因為可以減少不必要的寫入次數,時間複雜度同為 O(n),但實際寫入次數更少。
方法二:STL remove + erase(不符合原地要求,僅供了解)
使用 std::remove(nums.begin(), nums.end(), val) 將所有目標值移至尾部並回傳新尾端迭代器,再配合 nums.erase() 截斷。底層實作與雙指針相同,時間複雜度 O(n),但此題要求直接回傳新長度而非真正 erase,不適用於本題的判題方式。