👀樊梓慕：個人主頁

?🎥個人專欄：《C語言》《數(shù)據(jù)結(jié)構(gòu)》《藍(lán)橋杯試題》《LeetCode刷題筆記》《實訓(xùn)項目》《C++》《Linux》《算法》

🌝每一個不曾起舞的日子，都是對生命的辜負(fù)

---

目錄

前言

1.數(shù)組分塊（數(shù)組劃分）

移動零

復(fù)寫零

2.快慢雙指針（循環(huán)往復(fù)）

快樂數(shù)

3.對撞指針->暴力枚舉的優(yōu)化->利用單調(diào)性

盛最多水的容器

有效三角形的個數(shù)

4.對撞指針->兩數(shù)之和、三數(shù)之和、四數(shù)之和

兩數(shù)之和

三數(shù)之和

四數(shù)之和

---

前言

💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐

《算法》專欄正式掛牌成立

• 《算法》專欄主要是會系統(tǒng)的梳理一些OJ題的算法思想，將他們按照解題方法的不同劃分出來，然后歸納總結(jié)，當(dāng)然希望大家多多收藏，以后忘了可以常回來看看！? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐

本篇文章主要會講解雙指針的思想，雙指針是一種非常優(yōu)秀的算法思想，有對撞指針和快慢指針兩種基本用法。

雙指針對于有序數(shù)據(jù)的處理是比較有優(yōu)勢的，當(dāng)你遇到有序的數(shù)據(jù)時，你可以嘗試著利用雙指針或者二分來解題，當(dāng)然本篇文章只會講解雙指針。

那么雙指針?biāo)枷刖唧w的應(yīng)用，以及為什么雙指針適用于有序數(shù)組的處理呢？

---

歡迎大家📂收藏📂以便未來做題時可以快速找到思路，巧妙的方法可以事半功倍。

=========================================================================

GITEE相關(guān)代碼：🌟fanfei_c的倉庫🌟

=========================================================================

---

1.數(shù)組分塊（數(shù)組劃分）

數(shù)組分塊顧名思義，該類題目有一個特性就是將數(shù)組中的數(shù)據(jù)進(jìn)行分類，然后將分類的數(shù)據(jù)放在不同的區(qū)域上。

---

移動零

移動零 - 力扣（LeetCode）https://leetcode.cn/problems/move-zeroes/description/

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

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

?利用數(shù)組分塊的思想，我們可以將該數(shù)組劃分為三個區(qū)域：非零的已處理區(qū)域、零的已處理區(qū)域、待處理區(qū)域。

三個區(qū)域恰好可以利用兩個指針進(jìn)行分割得到。

所以我們定義兩個指針：

• cur：從左向右掃描數(shù)組（遍歷數(shù)組的作用），主要用來分割已處理區(qū)域和待處理區(qū)域用；
• dest：已處理的區(qū)域內(nèi)，非零元素的最后一個位置，主要用來分隔已處理區(qū)域內(nèi)部非零元素和零元素。

得到三個區(qū)間：

• 非零的已處理區(qū)域：[0,dest]
• 零的已處理區(qū)域：[dest+1,cur-1]
• 待處理區(qū)域：[cur,n-1]

?有了思路，畫圖獨立完成代碼，不要直接看博主的代碼。

class Solution {
public:void moveZeroes(vector<int>& nums) {for (int dest = -1, cur = 0; cur <= nums.size() - 1; cur++){//如果是零就跳過，不是零進(jìn)入if (nums[cur]){swap(nums[++dest], nums[cur]);}}}
};

---

復(fù)寫零

復(fù)寫零 - 力扣（LeetCode）https://leetcode.cn/problems/duplicate-zeros/description/

給你一個長度固定的整數(shù)數(shù)組?arr?，請你將該數(shù)組中出現(xiàn)的每個零都復(fù)寫一遍，并將其余的元素向右平移。

注意：請不要在超過該數(shù)組長度的位置寫入元素。請對輸入的數(shù)組?就地?進(jìn)行上述修改，不要從函數(shù)返回任何東西。

我們可以先嘗試著進(jìn)行異地復(fù)寫，然后嘗試著進(jìn)行原地復(fù)寫，看看會發(fā)生什么問題？

如果「從前向后」進(jìn)行原地復(fù)寫操作的話，由于0的出現(xiàn)會復(fù)寫兩次，導(dǎo)致沒有復(fù)寫的數(shù)「被覆
蓋掉」。

因此我們選擇「從后往前」的復(fù)寫策略。

但是「從后向前」復(fù)寫的時候，我們需要找到「最后一個復(fù)寫的數(shù)」，因此我們的大體流程分兩
步：

1. 先找到最后一個復(fù)寫的數(shù)；
2. 然后從后向前進(jìn)行復(fù)寫操作。

?這兩步仍然包含一些細(xì)節(jié)需要處理，比如會不會出現(xiàn)越界問題等？

• cur：用來遍歷數(shù)組用。
• dest：根據(jù)cur指向的指進(jìn)行移動一步或兩步，如果dest的位置處于最后一位或者已經(jīng)越界，跳出循環(huán)，如果是越界的情況，我們需要手動將其"拉回"，然后進(jìn)行從后向前的復(fù)寫操作。

有了思路，畫圖獨立完成代碼，不要直接看博主的代碼。

class Solution {
public:void duplicateZeros(vector<int>& arr) {int dest=-1,cur=0,n=arr.size();//1.先找到cur位置while(cur<n){if(arr[cur])dest++;elsedest+=2;if(dest>=n-1)//這里是為了及時檢測是否跳出break;cur++; }//1.5判斷dest位置if(dest==n){arr[dest-1]=0;dest-=2;cur--;}//2.然后向前復(fù)寫while(cur>=0){if(arr[cur])arr[dest--]=arr[cur--]; else{arr[dest--]=0;arr[dest--]=0;cur--;}}}
};

---

2.快慢雙指針（循環(huán)往復(fù)）

快慢雙指針基本思想：使用兩個移動速度不同的指針在數(shù)組或鏈表等序列結(jié)構(gòu)上移動。

一般什么情況下適用快慢雙指針的題目呢？

這種方法對于處理環(huán)形鏈表或數(shù)組非常有用，或者說循環(huán)往復(fù)的數(shù)據(jù)都比較適用快慢雙指針?biāo)惴▉磉M(jìn)行解決。

快樂數(shù)

快樂數(shù) - 力扣（LeetCode）https://leetcode.cn/problems/happy-number/description/

編寫一個算法來判斷一個數(shù)?n?是不是快樂數(shù)。

「快樂數(shù)」?定義為：

• 對于一個正整數(shù)，每一次將該數(shù)替換為它每個位置上的數(shù)字的平方和。
• 然后重復(fù)這個過程直到這個數(shù)變?yōu)?1，也可能是?無限循環(huán)?但始終變不到 1。
• 如果這個過程?結(jié)果為?1，那么這個數(shù)就是快樂數(shù)。

如果?n?是?快樂數(shù)?就返回?true?；不是，則返回?false?。

?請注意題目意義，只會有兩種情況：

• 情況1：無限循環(huán)但始終變不到1
• 情況2：有限次數(shù)內(nèi)，結(jié)果為1

所以對于這種循環(huán)往復(fù)的數(shù)據(jù)我們就可以聯(lián)想到快慢雙指針來做：

為了方便理解，我抽象的將數(shù)據(jù)做成鏈：

所以必然會成環(huán)，slow與fast必然會相遇，我們需要做的就是在他們相遇的時刻，檢測以下slow或者fast的值是否為1即可。

有了思路，畫圖獨立完成代碼，不要直接看博主的代碼。

class Solution {
public:int bitSum(int n) {int sum = 0;while (n) {int t = n % 10;sum += t * t;n /= 10;}return sum;}bool isHappy(int n) {int slow = n;int fast = bitSum(n);while (slow != fast) {slow = bitSum(slow);fast = bitSum(bitSum(fast));}return slow == 1;}
};

---

3.對撞指針->暴力枚舉的優(yōu)化->利用單調(diào)性

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

對撞指針從兩端向中間移動。?個指針從最左端開始，另?個從最右端開始，然后逐漸往中間逼
近。

對撞指針的終止條件一般是兩個指針相遇或者錯開（也可能在循環(huán)內(nèi)部找到結(jié)果直接跳出循
環(huán)），也就是：

• left == right（兩個指針指向同?個位置）
• left > right（兩個指針錯開）

---

?單調(diào)性解題的思路不好想到，但這是一種非常優(yōu)秀的對暴力枚舉方法的優(yōu)化思想。

盛最多水的容器

盛最多水的容器 - 力扣（LeetCode）https://leetcode.cn/problems/container-with-most-water/description/

給定一個長度為?n?的整數(shù)數(shù)組?height?。有?n?條垂線，第?i?條線的兩個端點是?(i, 0)?和?(i, height[i])?。

找出其中的兩條線，使得它們與?x?軸共同構(gòu)成的容器可以容納最多的水。

返回容器可以儲存的最大水量。

說明：你不能傾斜容器。

?如果說利用暴力枚舉的方式來做，很明顯你需要固定一邊，兩層for循環(huán)解決，時間復(fù)雜度O(N^2)，但這道題目作為一道中等難度的題，利用暴力枚舉必然會超時。

我們嘗試?yán)脤ψ仓羔樀姆绞絹碜?#xff1a;

w(寬)=right-left;

容積的計算公式：V=h*w

當(dāng)計算完一組結(jié)果之后，我們需要將左指針或右指針向中間移動，這樣如此反復(fù)就能得到最終答案，可是這樣并沒有降低時間復(fù)雜度，仍然是暴力枚舉的思路。

我們觀察：

當(dāng)左指針或右指針向中間移動時w是必然減小的。

又根據(jù)木桶原理，h取決于左右指針指向的值小的那一個數(shù)據(jù)。

本題是依據(jù)數(shù)據(jù)分析，進(jìn)而得到單調(diào)性的關(guān)系，需要大家自行畫圖分析，然后將思路轉(zhuǎn)化成代碼。

class Solution {
public:int maxArea(vector<int>& height) {int left=0;int right=height.size()-1;int v=0;int ret=0;while(left<right){int v=min(height[left],height[right])*(right-left);ret=max(v,ret);if(height[left]<height[right]) left++;else right--;}return ret;}
};

---

有效三角形的個數(shù)

有效三角形的個數(shù) - 力扣（LeetCode）https://leetcode.cn/problems/valid-triangle-number/description/

?給定一個包含非負(fù)整數(shù)的數(shù)組?nums?，返回其中可以組成三角形三條邊的三元組個數(shù)。

構(gòu)成三角形的條件：任意兩邊之和大于第三邊

但這個條件轉(zhuǎn)化成代碼需要三次判斷未免有些麻煩，所以我們可以將數(shù)組先進(jìn)行排序，排序之后如果較小的兩個值之和大于第三邊，那么就可以構(gòu)成三角形了。?

暴力枚舉的方式很顯然時間復(fù)雜度O(N^3)。

那我們嘗試著對數(shù)據(jù)進(jìn)行分析，看看能否利用單調(diào)性來優(yōu)化。

首先排序，我們將最大的數(shù)固定，然后利用對撞指針的思想進(jìn)行優(yōu)化。

?有了思路，畫圖獨立完成代碼，不要直接看博主的代碼。

class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());int n=nums.size();int maxIndex=n-1;int ret=0;while(maxIndex>=2){int left=0;int right=maxIndex-1;while(left<right){if(nums[left]+nums[right]>nums[maxIndex]){  ret+=right-left;right--;}else{left++;}}maxIndex--;}return ret;}
};

---

4.對撞指針->兩數(shù)之和、三數(shù)之和、四數(shù)之和

兩數(shù)之和

兩數(shù)之和 - 力扣（LeetCode）https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/description/

購物車內(nèi)的商品價格按照升序記錄于數(shù)組?price。請在購物車中找到兩個商品的價格總和剛好是?target。若存在多種情況，返回任一結(jié)果即可。

?首先我們發(fā)現(xiàn)數(shù)組是升序排列的，所以我們想到可以利用雙指針來解決，同樣的我們利用單調(diào)性，看看能否對暴力枚舉的策略作優(yōu)化。

暴力枚舉的時間復(fù)雜度很明顯O(N^2)。

兩數(shù)之和大于target時，利用單調(diào)性，令right--即可；

兩數(shù)之和小于target時，利用單調(diào)性，令left++即可；

兩數(shù)之和等于target時，我們將此時的結(jié)果尾插到結(jié)果數(shù)組中。

class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {int left=0;int right=price.size()-1;vector<int> ret;while(left<right){int sum=price[left]+price[right];if(sum<target) left++;else if(sum>target) right--;else{ret.push_back(price[left]);ret.push_back(price[right]);break;}}return ret;}
};

---

三數(shù)之和

三數(shù)之和 - 力扣（LeetCode）https://leetcode.cn/problems/3sum/description/

給你一個整數(shù)數(shù)組?nums?，判斷是否存在三元組?[nums[i], nums[j], nums[k]]?滿足?i != j、i != k?且?j != k?，同時還滿足?nums[i] + nums[j] + nums[k] == 0?。請

你返回所有和為?0?且不重復(fù)的三元組。

注意：答案中不可以包含重復(fù)的三元組。

?本題可以借助兩數(shù)之和的思想進(jìn)行解題，無非就是需要多加一層循環(huán)，將第三個數(shù)固定即可。

另外的兩個數(shù)仍然為兩數(shù)之和的思想，只不過此時兩數(shù)之和等于負(fù)的第三個數(shù)。

難點：注意本題要求去重，并且要求返回所有滿足的數(shù)據(jù)，所以我們需要處理一些細(xì)節(jié)問題。

首先，關(guān)于返回所有：

• 當(dāng)找到一種結(jié)果后，不能直接返回，要繼續(xù)縮小區(qū)間繼續(xù)尋找。

其次，關(guān)于去重：

• 找到一種結(jié)果之后，left和right要跳過重復(fù)元素。
• 當(dāng)使用完一次雙指針?biāo)惴ê?#xff0c;即更換第三個數(shù)時，也要跳過重復(fù)元素。
• 注意防止越界。

---

??有了思路，畫圖獨立完成代碼，不要直接看博主的代碼。

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(), nums.end());vector<vector<int>> ret;int n = nums.size();for (int i = 0; i < n;){if (nums[i] > 0) break;//小優(yōu)化int left = i + 1, right = n - 1, target = -nums[i];while (left < right){int sum = nums[left] + nums[right];if (sum < target) left++;else if (sum > target) right--;else{ret.push_back({ nums[left++],nums[right--],nums[i] });//去重 left 和 rightwhile (left < right && nums[left] == nums[left - 1]) left++;while (left < right && nums[right] == nums[right + 1]) right--;}}//去重 ii++;while (i < n && nums[i] == nums[i - 1]) i++;}return ret;}
};

---

四數(shù)之和

四數(shù)之和 - 力扣（LeetCode）https://leetcode.cn/problems/4sum/description/

給你一個由?n?個整數(shù)組成的數(shù)組?nums?，和一個目標(biāo)值?target?。請你找出并返回滿足下述全部條件且不重復(fù)的四元組?[nums[a], nums[b], nums[c], nums[d]]?（若兩個四元組元素一一對應(yīng)，則認(rèn)為兩個四元組重復(fù)）：

• 0 <= a, b, c, d?< n
• a、b、c?和?d?互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按?任意順序?返回答案 。

?四數(shù)之和是三數(shù)之和的升級，本質(zhì)上沒有任何區(qū)別，只不過多加了一個需要固定的數(shù)，多加了一層循環(huán)而已，如果你已經(jīng)掌握了三數(shù)之和，那么這道題對你來說會非常簡單。

?有了思路，畫圖獨立完成代碼，不要直接看博主的代碼。

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {sort(nums.begin(),nums.end());vector<vector<int>> ret;int n=nums.size();for(int i=0;i<n;){for(int j=i+1;j<n;){int left=j+1,right=n-1; long long num=(long long)target-nums[j]-nums[i];//需要注意的細(xì)節(jié)while(left<right){int sum=nums[left]+nums[right];if(sum>num) right--;else if(sum<num) left++;else{ret.push_back({nums[i],nums[j],nums[left++],nums[right--]});//去重 left 和 rightwhile(left<right && nums[left]==nums[left-1]) left++;while(left<right && nums[right]==nums[right+1]) right--;}}//去重 jj++;while(j<n && nums[j]==nums[j-1]) j++;}//去重ii++;while(i<n && nums[i]==nums[i-1]) i++;}return ret;}
};

---

以上就是雙指針?biāo)惴ㄔ趯嶋H題目中的應(yīng)用，總的來說，雙指針?biāo)惴ㄊ潜容^基礎(chǔ)并且簡單的算法。

大家只需要記住：當(dāng)所給數(shù)據(jù)為有序時，不妨考慮用雙指針?biāo)惴ㄟM(jìn)行解決。

---

🐸簡單總結(jié)🐸

雙指針擅于處理有序數(shù)據(jù)，可以解決數(shù)組分塊、循環(huán)往復(fù)數(shù)據(jù)可以利用快慢指針?biāo)枷?#xff08;得到某個值可以理解為在某個值處循環(huán)）、對撞指針結(jié)合單調(diào)性可以優(yōu)化暴力枚舉（注意細(xì)節(jié)：去重和不漏）。

---

=========================================================================

如果你對該系列文章有興趣的話，歡迎持續(xù)關(guān)注博主動態(tài)，博主會持續(xù)輸出優(yōu)質(zhì)內(nèi)容

🍎博主很需要大家的支持，你的支持是我創(chuàng)作的不竭動力🍎

🌟~ 點贊收藏＋關(guān)注 ~🌟

=========================================================================