目錄
- 零、題目描述
- 一、為什么這道題值得你花幾分鐘看懂？
- 二、題目拆解：提取其中的關鍵點
- 三、明確思路：雙指針的巧妙配合
- 四、算法實現：雙指針的代碼演繹
- 五、C++代碼實現：一步步拆解
- 代碼拆解
- 時間復雜度和空間復雜度
- 六、實現過程中的坑點總結
- 七、舉一反三
零、題目描述
題目鏈接：移動零
題目描述：
示例 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
一、為什么這道題值得你花幾分鐘看懂？
如果你正在打磨自己的算法基礎，那「移動零」這道題你一定不能錯過——它是 LeetCode 第 283 題，更是雙指針技巧的經典入門題，幾乎所有算法入門教程都會拿它舉例。
從算法能力提升來講，這道題能幫你深刻理解雙指針在原地修改數組中的核心作用，掌握「快慢指針配合」的精髓。這種技巧不僅能解決數組中的元素移動問題，還能延伸到鏈表操作、滑動窗口等多種場景，是很多高效算法的基礎。
甚至在實際開發中，當需要對數據進行過濾、整理，又希望節省空間時，雙指針的思路能幫你寫出更高效、更優雅的代碼。
二、題目拆解：提取其中的關鍵點
先看原題：
給定一個數組 nums，編寫一個函數將所有 0 移動到數組的末尾，同時保持非零元素的相對順序。必須在不復制數組的情況下原地對數組進行操作。
再結合所給的代碼框架和提示：
class Solution {
public:void moveZeroes(vector<int>& nums) {}
};
核心要素提煉：
- 輸入是一個整數類型的向量
nums，需要對其進行原地修改。 - 操作目標是將數組中的所有
0移到末尾，同時保證非零元素的相對順序不變。 - 不能使用額外的數組來輔助，必須在原數組上進行操作。
關鍵點：
- 雙指針應用：用兩個指針分別追蹤非零元素的位置和當前遍歷的位置。
- 元素交換：將非零元素移動到前面合適的位置。
- 保持順序：確保非零元素的相對位置和原來一致。
- 原地操作：不使用額外的數組空間，只在原數組上進行修改。
三、明確思路：雙指針的巧妙配合
1. 最直觀的想法：先移非零，再補零
拿到題的第一反應：把所有非零元素按順序移到數組前面，然后把剩下的位置都填上0。比如對于數組[0,1,0,3,12]，先把非零元素1、3、12依次移到前面，得到[1,3,12,...]，再把后面的位置補成0，結果就是[1,3,12,0,0]。
這種思路的關鍵是如何高效地找到非零元素應該放置的位置，這就需要用到雙指針了。
2. 雙指針的分工
在這里，我們可以用兩個指針：
cur指針：負責遍歷整個數組，尋找非零元素，相當于“探索者”。dest指針：負責記錄下一個非零元素應該放置的位置，相當于“占位者”。
初始時，cur從數組開頭開始遍歷，dest指向-1（表示還沒有確定非零元素的位置）。當cur遇到非零元素時，就把dest向前移動一位，然后交換cur和dest指向的元素。這樣，dest始終指向已經處理好的非零元素的最后一個位置。
舉個例子（示例1）：
初始數組：[0,1,0,3,12]，cur=0，dest=-1
cur=0，元素是0，不做操作，cur++
cur=1，元素是1（非零），dest++變為0，交換nums[0]和nums[1]，數組變為[1,0,0,3,12]，cur++
cur=2，元素是0，不做操作，cur++
cur=3，元素是3（非零），dest++變為1，交換nums[1]和nums[3]，數組變為[1,3,0,0,12]，cur++
cur=4，元素是12（非零），dest++變為2，交換nums[2]和nums[4]，數組變為[1,3,12,0,0]，cur++
遍歷結束，得到結果
3. 為什么這樣可行？
因為cur指針一直在dest指針前面或者和它同步，dest指針前面的元素都是已經處理好的非零元素，并且保持著原來的相對順序。當cur遇到非零元素時，把它交換到dest+1的位置，就保證了非零元素按原來的順序排列在前面，而后面剩下的位置自然都是0了。
這種方法只需要遍歷一次數組，并且是原地操作，時間復雜度是O(n)，空間復雜度是O(1)，非常高效。
四、算法實現：雙指針的代碼演繹
這道題我用雙指針的方法來實現，下面講解具體的算法思路。
核心邏輯：
用cur指針遍歷數組，當遇到非零元素時，將dest指針向前移動一位，然后交換cur和dest指向的元素，這樣就能把非零元素逐步移到前面，零自然就到后面去了。
步驟拆解：
- 初始化
cur為0，dest為-1。 - 用
cur遍歷數組中的每個元素：- 若
nums[cur]是非零元素：- 將
dest向前移動一位（dest++）。 - 交換
nums[cur]和nums[dest]。
- 將
cur向前移動一位（cur++）。
- 若
- 遍歷結束后，數組中的所有零都被移到了末尾，非零元素保持相對順序不變。
雙指針細節：
cur指針：從0開始，依次遍歷數組的每個元素，直到數組末尾。它的作用是發現非零元素。dest指針：初始值為-1，表示還沒有非零元素被放置。每當cur找到一個非零元素，dest就向前移動一位，指向這個非零元素應該放置的位置。- 交換操作：當
cur找到非零元素時，交換nums[cur]和nums[dest]，這樣非零元素就被放到了前面合適的位置。 - 遍歷順序：
cur始終從左到右遍歷，保證了非零元素的相對順序不變。
五、C++代碼實現：一步步拆解
完整代碼（附詳細注釋）：
#include <vector>
using namespace std;class Solution {
public:void moveZeroes(vector<int>& nums) {int n = nums.size();// cur用于遍歷數組，dest用于記錄非零元素應放的位置for (int cur = 0, dest = -1; cur < nums.size(); cur++) {if (nums[cur] != 0) { // 遇到非零元素dest++; // dest移動到下一個位置swap(nums[dest], nums[cur]); // 交換元素，將非零元素放到前面}}}
};
代碼拆解
1. 變量初始化
int n = nums.size(); // 獲取數組長度，雖然這里沒有直接使用，但可以用于后續擴展
int cur = 0; // 遍歷指針，從數組開頭開始
int dest = -1; // 目標指針，初始為-1，表示還沒有非零元素被放置
作用：cur負責遍歷整個數組，dest負責跟蹤非零元素應該放置的位置，初始狀態下還沒有非零元素被處理，所以dest為-1。
2. 主循環邏輯
for (int cur = 0, dest = -1; cur < nums.size(); cur++) {// 循環條件：cur遍歷完數組的所有元素if (nums[cur] != 0) { // 當遇到非零元素時dest++; // 目標位置向前移動一位swap(nums[dest], nums[cur]); // 交換元素，將非零元素放到目標位置}// 如果是零元素，則不做處理，cur繼續向前移動
}
核心設計：
- 遍歷機制：
cur從0開始，每次循環后自增1，直到遍歷完整個數組，確保每個元素都被檢查。 - 非零元素處理：當
nums[cur]不是0時，說明找到了一個需要放到前面的元素。此時dest先自增1，指向當前應該放置非零元素的位置，然后交換nums[cur]和nums[dest]，這樣非零元素就被放到了前面。 - 零元素處理：當
nums[cur]是0時，不做任何操作，cur繼續向前移動，零元素就被留在了原地，最終會被后面的非零元素交換到后面去。
示例走讀（示例1：nums = [0,1,0,3,12]）
| 步驟 | cur | dest | nums[cur] | 操作 | 數組狀態 |
|---|---|---|---|---|---|
| 初始 | 0 | -1 | 0 | 不操作，cur++ | [0,1,0,3,12] |
| 1 | 1 | -1 | 1 | dest++變為0，交換nums[1]和nums[0]，cur++ | [1,0,0,3,12] |
| 2 | 2 | 0 | 0 | 不操作，cur++ | [1,0,0,3,12] |
| 3 | 3 | 0 | 3 | dest++變為1，交換nums[3]和nums[1]，cur++ | [1,3,0,0,12] |
| 4 | 4 | 1 | 12 | dest++變為2，交換nums[4]和nums[2]，cur++ | [1,3,12,0,0] |
| 結束 | 5（退出循環） | 2 | - | - | [1,3,12,0,0] |
通過這個過程可以清晰地看到，非零元素1、3、12依次被放到了數組前面，零元素被移到了后面，并且非零元素的相對順序保持不變。
時間復雜度和空間復雜度
| 復雜度類型 | 具體值 | 說明 |
|---|---|---|
| 時間復雜度 | O(n) | n是數組的長度，cur指針遍歷整個數組一次，每個元素最多被交換一次 |
| 空間復雜度 | O(1) | 只使用了兩個額外的指針變量，沒有使用額外的數組或其他數據結構 |
這種算法在時間和空間上都非常高效，符合題目的要求。
六、實現過程中的坑點總結
-
dest指針的初始值
錯誤寫法：for (int cur = 0, dest = 0; cur < nums.size(); cur++) {// ... }問題：如果
dest初始化為0，當數組的第一個元素是非零元素時，會把它和自己交換，雖然結果正確，但做了無用功。更重要的是，如果數組全是零元素，可能會出現不必要的操作。
正確做法：初始化為-1，讓第一個非零元素能正確地放到索引0的位置。 -
忘記交換元素
錯誤寫法：if (nums[cur] != 0) {dest++;nums[dest] = nums[cur]; // 直接賦值，沒有處理原來的位置 }問題：這樣會導致原來
dest位置的元素被覆蓋，而cur位置的非零元素沒有被清除，可能會留下重復的值。
正確做法：使用swap函數交換兩個位置的元素，確保非零元素移動的同時，零元素被換到后面。 -
遍歷順序錯誤
錯誤寫法：for (int cur = nums.size() - 1; cur >= 0; cur--) {// ... }問題：從后往前遍歷會打亂非零元素的相對順序，無法保證移動后非零元素的順序和原來一致。
正確做法：cur指針必須從左到右遍歷數組，才能保證非零元素的相對順序不變。 -
處理空數組或只有一個元素的情況
雖然代碼中沒有專門處理，但當前的代碼邏輯對這些情況是兼容的：- 如果數組為空，循環不會執行，直接返回。
- 如果數組只有一個元素，無論是0還是非零，循環執行一次后都會得到正確的結果。
-
不必要的交換
當cur和dest相等時（比如數組開頭都是非零元素），交換操作是不必要的。可以添加一個判斷來優化：if (nums[cur] != 0) {dest++;if (cur != dest) { // 只有當位置不同時才交換swap(nums[dest], nums[cur]);} }這樣可以減少一些無用的交換操作，提高代碼效率。
七、舉一反三
學會這道題的雙指針技巧，你能解決很多類似的數組操作問題：
- LeetCode 27. 移除元素：給定一個值，移除數組中所有等于這個值的元素，思路是用雙指針將不等于該值的元素移到前面。
- LeetCode 26. 移除重復元素：刪除有序數組中的重復項，讓每個元素只出現一次，用雙指針可以高效地實現。
- LeetCode 80. 刪除有序數組中的重復項 II：允許元素最多出現兩次，雙指針的思路可以擴展應用。
明天我們一起討論LeetCode 1089. 復寫零這道題有興趣的朋友可以提前思考下
雙指針技巧在數組和鏈表操作中非常常見，掌握它能讓你在處理元素移動、刪除、查找等問題時更加得心應手。
最后，歡迎大家在評論區分享自己的代碼和思路，一起交流學習~ 如果你有更巧妙的方法，也請不吝賜教，我會認真學習并回復的！
這是今天的封面原圖：
 155. 最小棧 （棧）)
)
