目錄

雙指針?biāo)惴ㄖv解

移動零

---

雙指針?biāo)惴ㄖv解

常見的雙指針有兩種形式，一種是對撞指針，一種是快慢指針。

對撞指針：一般用于順序結(jié)構(gòu)中，也稱左右指針。

1. 對撞指針從兩端向中間移動。一個指針從最左端開始，另一個從最右端開始，然后逐漸往中間逼近。
2. 對撞指針的終止條件一般是兩個指針相遇或者錯開（也可能在循環(huán)內(nèi)部找到結(jié)果直接跳出循環(huán)），也就是：

1. 1. left == right （兩個指針指向同一個位置）
   2. left > right （兩個指針錯開）

快慢指針：又稱龜兔賽跑賽跑算法，其基本思想就是使用兩個移動速度不同的指針在數(shù)組或鏈表等序列結(jié)構(gòu)上移動

這種方法對于處理環(huán)形鏈表或數(shù)組非常有用。

其實不單單是環(huán)形鏈表或者是數(shù)組，如果我們要研究的問題出現(xiàn)循環(huán)往復(fù)的情況，均可考慮使用快慢指針的思想。

快慢指針的實現(xiàn)方式有很多種，最常用的一種就是：

·在一次循環(huán)中，每次讓慢的指針向移動一位，而快的指針往后移動兩位，實現(xiàn)一快一慢。

移動零

「數(shù)組分兩塊」是非常常見的一種題型，主要就是根據(jù)一種劃分方式，將數(shù)組的內(nèi)容分成左右兩部分。這種類型的題，一般就是使用「雙指針」來解決

題目鏈接：283.移動零

給定一個數(shù)組?nums，編寫一個函數(shù)將所有?0?移動到數(shù)組的末尾，同時保持非零元素的相對順序。

請注意?，必須在不復(fù)制數(shù)組的情況下原地對數(shù)組進行操作。

解法：（快排的思想：數(shù)組劃分區(qū)間-數(shù)組分兩塊）：

算法思路：

在本題中，我們可以用一個 cur 指針來掃描整個數(shù)組，另一個 dest 指針用來記錄非零數(shù)序列的最后一個位置。根據(jù)cur在掃描的過程中，遇到不同的情況，分類處理，實現(xiàn)數(shù)組的劃分。以下是我們的目標(biāo)

我們?nèi)绾螌崿F(xiàn)這種呢？

1.cur 指針的目的是遍歷數(shù)組，那么cur指針一定是在數(shù)組首元素位置

2.既然cur指針在首元素，為了實現(xiàn)數(shù)組被劃分三個階段，那么des只能在cur之前的位置也就是 -1 處。

3.cur指針開始向后移動，為了實現(xiàn)【des+1 ，cur-1】中間是0，那么控制cur的條件就是，cur遇到0就跳過，也就是繼續(xù)往前走。如果遇到了不是0，那么就將des+1，進行交換，交換后cur當(dāng)前位置就變成了0，繼續(xù)加加，直到遍歷完數(shù)組。

因此可以簡化思想：

cur 從前往后遍歷過程中：

1.遇到0元素：cur++

2.遇到非0元素：1??swap(++des;cur)?2???cur++

void moveZeroes(vector<int>& nums) {int cur = 0;int des = -1;while(cur < nums.size()){//cur是0就跳過if(nums[cur] == 0) cur++;else{//不是0就交換，在++swap(nums[++des],nums[cur]);cur++;}}
}

也可以用for循環(huán)

void moveZeroes(vector<int>& nums) {for(int cur = 0,des = -1;cur < nums.size();cur++){if(nums[cur])//處理非0元素{swap(nums[++des],nums[cur]);}}}