?
一、介紹雙指針算法
????????雙指針（或稱為雙索引）算法是一種高效的算法技巧，常用于處理數組或鏈表等線性數據結構。它通過使用兩個指針來遍歷數據，從而減少時間復雜度，避免使用嵌套循環。雙指針算法在解決諸如查找、排序、去重等問題時非常有效。
1.雙指針算法的基本思想
????????雙指針算法的核心思想是通過兩個指針（通常是索引）來遍歷數組或鏈表，而不是使用嵌套循環。這兩個指針可以是：
快慢指針：一個指針移動速度比另一個快。
左右指針：兩個指針從數組的兩端向中間移動。
前后指針：兩個指針從同一個方向移動，但速度或條件不同。
2.常見的雙指針應用場景
1.?快慢指針
快慢指針常用于檢測環、找到鏈表的中間節點等。
示例：檢測鏈表中是否有環
#include <iostream>
using namespace std;struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};bool hasCycle(ListNode* head) {ListNode* slow = head;ListNode* fast = head;while (fast != nullptr && fast->next != nullptr) {slow = slow->next;fast = fast->next->next;if (slow == fast) {return true; // 發現環}}return false; // 沒有環
}2.?左右指針
左右指針常用于數組的兩端向中間遍歷，例如在排序數組中查找兩個數的和。
示例：兩數之和等于目標值
#include <iostream>
#include <vector>
using namespace std;vector<int> twoSum(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while (left < right) {int sum = nums[left] + nums[right];if (sum == target) {return {left, right};} else if (sum < target) {left++;} else {right--;}}return {};
}3.?前后指針
前后指針常用于處理滑動窗口問題或數組中的去重問題。
示例：移除重復項
#include <iostream>
#include <vector>
using namespace std;int removeDuplicates(vector<int>& nums) {if (nums.empty()) return 0;int i = 0; // 前指針for (int j = 1; j < nums.size(); ++j) { // 后指針if (nums[j] != nums[i]) {i++;nums[i] = nums[j];}}return i + 1; // 返回新數組的長度
}3.雙指針算法的優點
時間復雜度低：通常可以將時間復雜度從 O(n2) 降低到 O(n)。
空間復雜度低：不需要額外的存儲空間，通常為 O(1)。
邏輯清晰：代碼簡潔，易于理解和實現。
4.雙指針算法的局限性
適用范圍有限：主要用于線性數據結構，如數組和鏈表。
需要預排序：某些問題（如兩數之和）需要先對數組進行排序。
5.總結
????????雙指針算法是一種非常實用的技巧，適用于多種問題場景。通過合理使用雙指針，可以顯著提高算法的效率，減少不必要的計算。在實際應用中，需要根據具體問題選擇合適的指針策略（如快慢指針、左右指針等）。
二、實戰——題目練習
例一（前后指針）61. 最長不含重復字符的子字符串 - AcWing題庫??????
問題描述
請從字符串中找出一個最長的不包含重復字符的子字符串，計算該最長子字符串的長度。
假設字符串中只包含從?
a?到?z?的字符。數據范圍
輸入字符串長度 [0,1000]。
樣例
輸入："abcabc"輸出：3
?思路：
使用雙指針算法，根據觀察發現，當使用i,j兩個快慢指針表示當前的指針移動到i的最長不重復序列時候，具有單調性，即i向后移動，j必然向右或者不動，不可能向左移動，這一單調性質導致可以使用雙指針算法。
當快指針所指元素在兩指針區間中重復，則慢指針向右移動，直到快指針所指元素在兩指針區間不充復。?每移動一次計算一下不重復字串的長度，并與已有長度比較取最大值.
🌟 滑動窗口法：最長無重復子串的奇妙冒險 🌟
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;class Solution {
public:int longest(string str) {int st[26] = {0}; // 📖 字符賬本：記錄26個字母的出現次數（假設只有小寫字母）int res = 0; // 🏆 冠軍記錄：存儲當前找到的最長子串長度int j = 0; // 🚪 左門衛：維護窗口左邊界// 🚀 右門衛i的探險之旅：逐個檢查字符串中的字符for (int i = 0; i < str.size(); i++) {// 📌 步驟1：新字符進賬本（比如讀到'a'，st[0]加1）st[str[i] - 'a']++;// 🚧 步驟2：發現重復！左門衛開始清理門戶// 當新字符導致重復（賬本中該字符數量>1）while (j < i && st[str[i] - 'a'] > 1) {st[str[j] - 'a']--; // 🧹 左門衛掃過的字符從賬本擦除j++; // 🚶♂? 左門衛右移一步}// 📏 步驟3：測量當前窗口長度，刷新冠軍記錄res = max(res, i - j + 1); // ? 比如i=2,j=0時長度是3}return res; // 🏁 返回最終找到的最長長度}
};int main() {Solution ans;string str;cin >> str; int result = ans.longest(str);cout << result << endl; return 0;
}🎮 生動比喻：貪吃蛇版滑動窗口
想象你控制著一條貪吃蛇在字符串上爬行：
-
蛇頭（右指針i）：不斷向前吞噬字符
-
蛇尾（左指針j）：當吃到重復字符時，蛇尾會收縮直到吐出重復的字符
-
蛇身：當前窗口內的字符就是蛇的身體
-
限制規則：蛇的身體不能有重復的字符部件
示例過程：字符串?"abca"
-
🐍 蛇吃下 a → 長度1
-
🐍 蛇吃下 b → 長度2
-
🐍 蛇吃下 c → 長度3
-
🐍 蛇吃下 a → 檢測到重復！
-
蛇尾開始收縮：吐出第一個a → 長度變為3（bca）
-
🧠 核心原理詳解
| 步驟 | 操作 | 作用 | 時間復雜度 |
|---|---|---|---|
| 1?? | 右指針擴張 | 探索新字符，擴大窗口右邊界 | O(n) |
| 2?? | 檢測重復并收縮左邊界 | 確保窗口內字符唯一 | 總計O(n) |
| 3?? | 實時更新最大長度 | 記錄歷史最大值 | O(1) |
時空復雜度：
-
??時間：左右指針各遍歷一次字符串 → O(2n) ≈?O(n)
-
💾?空間：固定長度的字符計數器 →?O(1)
🌰 舉個栗子：處理 "abcabcbb"
| 右指針i | 當前字符 | 窗口區間 | 操作 | 當前長度 | 最大長度 |
|---|---|---|---|---|---|
| 0 | a | [0,0] | 記錄a | 1 | 1 |
| 1 | b | [0,1] | 記錄b | 2 | 2 |
| 2 | c | [0,2] | 記錄c | 3 | 3 |
| 3 | a | [0,3] | 發現a重復，收縮窗口到[1,3] | 3 | 3 |
| ... | ... | ... | ... | ... | ... |
最終找到最長無重復子串長度為3（"abc"或"bca"）
🚨 注意事項
-
字符范圍：代碼假設輸入為小寫字母，若需支持更多字符需擴大數組大小
-
邊界情況：完美處理空字符串（返回0）、全相同字符等情況
-
移動邏輯：左指針的移動是跳躍式的，而非逐步移動，確保高效性
這個算法就像兩個默契的探險隊員，一個開拓疆土，一個鞏固后方，共同找到最長的純凈領地！ 🏔?
例二（前后指針）
問題描述
給定一個長度為 n 的整數序列，請找出最長的不包含重復的數的連續區間，輸出它的長度。
輸入格式
第一行包含整數 n。
第二行包含 n 個整數（均在 0～1e5 范圍內），表示整數序列。
輸出格式
共一行，包含一個整數，表示最長的不包含重復的數的連續區間的長度。
數據范圍
1≤n≤1e5
樣例輸入
5
1 2 2 3 5樣例輸出
3
🎪 超市排隊買水果模型 —— 滑動窗口原理詳解
🌟 代碼原理（生動比喻版）
想象你正在超市排隊買水果，規則是：必須選擇連續的一籃水果，且每種水果只能出現一次。你需要找到最長的合格水果籃長度。
角色分配：
-
收銀員小姐姐 (指針i)：不斷掃描新水果放入購物籃右端
-
理貨員小哥 (指針j)：當發現重復水果時，從購物籃左端拿出水果
-
智能標簽 (mid數組)：實時統計每種水果在購物籃中的數量
工作流程：
-
收銀員每拿到一個新水果（i右移），就在標簽上+1
-
當發現某個水果數量>1（重復），理貨員開始從左邊拿出水果（j右移），直到重復水果被拿出
-
每次操作后測量購物籃長度，記錄歷史最大值
🧩 代碼逐行解析（帶詳細注釋）
#include<bits/stdc++.h>
using namespace std;
const int N =100010; // 最大水果種類數（假設水果編號不超過10萬）
int arr[N], mid[N], n; // arr-水果隊列，mid-水果計數表，n-總水果數class Solution{
public:int longest(){int res = 0; // 記錄最長無重復水果籃長度// 🛒 開始掃描水果隊列（i是右邊界，j是左邊界）for(int i=0, j=0; i<n; i++) {mid[arr[i]]++; // 🏷? 將新水果加入計數表（比如蘋果+1）// 🚨 發現重復！開始調整左邊界（類似超市警報響起）while(j<i && mid[arr[i]] > 1) {mid[arr[j]]--; // 🧹 把最左邊的水果拿出籃子j++; // 📏 左邊界右移（購物籃縮短）}// 📐 計算當前購物籃長度，更新最大值res = max(res, i-j+1); }return res; // 🏆 返回最終找到的最大長度}
}; int main()
{Solution ans;cin >> n; // 輸入總水果數// 🍎 輸入水果隊列（比如：蘋果2 香蕉3 蘋果2 橙子4）for(int i=0; i<n; i++) cin >> arr[i]; int end = ans.longest(); // 🧮 計算最長無重復區段cout << end << endl; // 📢 輸出結果return 0;
}🌰 舉個栗子：處理序列 [2,3,2,4]
| 步驟 | 當前水果 | 購物籃內容 | 操作 | 當前長度 | 最大長度 |
|---|---|---|---|---|---|
| 1 | 2 | [2] | 正常放入 | 1 | 1 |
| 2 | 3 | [2,3] | 正常放入 | 2 | 2 |
| 3 | 2 | [2,3,2] | 發現重復！ | - | - |
| ?? 拿出左邊第一個2 | [3,2] | 2 | |||
| 4 | 4 | [3,2,4] | 正常放入 | 3 | 3 |
最終結果：3（對應子序列 [3,2,4]）
🚨 注意事項（常見疑問解答）
-
為什么用
while不用if？-
就像超市可能連續拿出多個水果才能消除重復，比如序列 [1,2,1,1] 需要移動j兩次
-
-
數組越界問題？
-
代碼假設水果編號在0-10萬之間，實際使用應根據題目要求調整mid數組大小
-
-
時間復雜度：
-
左右指針各掃描一次，時間復雜度 O(n)，比暴力法 O(n2) 高效得多
-
-
空數組處理：
-
當n=0時，返回0，符合邏輯
-
這個算法就像兩個默契的超市員工，一個不斷擴展貨架，一個及時整理貨物，共同找到最完美的商品陳列方案！ 🛒?
例三（左右指針）
1. 題目描述
給定兩個升序排序的有序數組 A 和 B，以及一個目標值 x。數組下標從 0 開始。請你求出滿足 A[i]+B[j]=x 的數對 (i,j)。
數據保證有唯一解。
輸入格式
第一行包含三個整數 n,m,x，分別表示 A 的長度，B 的長度以及目標值 x。第二行包含 n 個整數，表示數組 A。
第三行包含 m 個整數，表示數組 B。
輸出格式
共一行，包含兩個整數 i 和 j。數據范圍
數組長度不超過 1e5。
同一數組內元素各不相同。
1≤數組元素≤1e9輸入樣例：
4 5 6
1 2 4 7
3 4 6 8 9輸出樣例：
1 1
代碼展示?
#include<bits/stdc++.h>
using namespace std;const int N = 100010; // 定義常量N，用于數組的最大長度
int a[N], b[N]; // 定義兩個數組a和b
int n, m, target; // 定義變量n表示數組a的長度，m表示數組b的長度，target表示目標值class Solution {
public:vector<int> targetsum() {for (int i = 0, j = m - 1; i < n; i++) { // 初始化i指向數組a的第一個元素，j指向數組b的最后一個元素while (j >= 0 && a[i] + b[j] > target) { // 如果a[i] + b[j]大于目標值，說明b[j]過大，需要減小jj--;}if (a[i] + b[j] == target) return {i, j}; // 如果找到符合條件的數對，返回索引對(i, j)}return {}; // 根據題意，這里不會執行，因為保證有唯一解}
};int main() {Solution ans; // 創建Solution類的對象anscin >> n >> m >> target; // 輸入數組a的長度n，數組b的長度m，以及目標值targetfor (int i = 0; i < n; i++) cin >> a[i]; // 輸入數組a的所有元素for (int i = 0; i < m; i++) cin >> b[i]; // 輸入數組b的所有元素vector<int> end = ans.targetsum(); // 調用targetsum函數，得到結果cout << end[0] << " " << end[1] << endl; // 輸出結果中的索引對return 0;
}這段代碼使用雙指針技巧高效地尋找兩個升序數組中滿足和為給定目標值的元素對。以下是其原理的詳細解釋：
核心思路：
雙指針策略：設定兩個指針i和j，i從數組A的起始位置開始（i=0），j從數組B的末尾開始（j=m-1）。
利用有序性：由于數組是升序排列，當i增大時A[i]的值變大，此時為了保持總和接近目標值，必須減小B[j]的值（即j左移）。
指針移動邏輯：
對于每個A[i]，不斷左移j直到A[i] + B[j] ≤ 目標值。
若此時和等于目標值，立即返回這對下標。
若和仍小于目標值，則i右移以增大總和。
步驟詳解：
初始化指針：i指向A的最小元素（頭），j指向B的最大元素（尾）。
調整j的位置：對于當前A[i]，若A[i]+B[j]過大，則不斷左移j，直到找到合適的B[j]使和不超過目標。
檢查匹配：若找到和正好等于目標值的組合，立即返回結果。
遞增i：若當前組合不滿足，i右移以嘗試更大的A元素，同時j保持在上次調整后的位置（無需重置）。
算法優勢：
時間復雜度O(n+m)：每個元素最多被訪問一次，高效處理大規模數據。
空間復雜度O(1)：僅使用固定數量的變量，無需額外存儲。
我們可以將這個問題類比成兩人合作調整天平平衡的場景，幫助理解雙指針的工作原理：
📖 生活場景類比
想象你和小伙伴在實驗室調整一架天平。天平左側的砝碼盒（數組A）按重量從小到大排列，右側的砝碼盒（數組B）按重量從大到小排列。你們需要各選一個砝碼，使得兩側砝碼的總重量剛好等于目標值?x。
操作規則：
你的策略（指針i）：從左側砝碼盒最輕的開始（
i=0），依次嘗試更重的砝碼。小伙伴的策略（指針j）：從右側砝碼盒最重的開始（
j=m-1），依次嘗試更輕的砝碼。
動態調整過程：
情況1：總和太重
當你選中左側的砝碼?A[i]?時，小伙伴發現當前右側的砝碼?B[j]?加上你的選擇后總重量超過了目標值?x。此時小伙伴會主動換一個更輕的右側砝碼（j--），直到總重量不再超標。情況2：總和合適
如果調整后的?A[i] + B[j]?正好等于?x，兩人立刻停止，成功找到解！情況3：總和太輕
如果調整到最輕的右側砝碼后，總重量仍不足，你會換一個更重的左側砝碼（i++），而小伙伴保持當前右側砝碼的位置繼續配合。
🌟 類比與代碼的映射
| 生活場景 | 代碼邏輯 | 意義 |
|---|---|---|
| 左側砝碼盒（從小到大排列） | 數組?A?升序排列 | 指針?i?從左向右移動，嘗試更大的值 |
| 右側砝碼盒（從大到小排列） | 數組?B?升序排列，但指針?j?從右向左移動 | 指針?j?從右向左移動，嘗試更小的值 |
| 兩人實時溝通調整策略 | 雙指針?i?和?j?協同移動 | 通過反向移動縮小搜索范圍 |
| 找到平衡點后停止 | 返回?{i, j} | 確保唯一解被高效定位 |
📝 代碼注釋與生活場景結合
vector<int> targetsum() {for (int i = 0, j = m - 1; i < n; i++) { // 你從最輕的左側砝碼開始嘗試while (j >= 0 && a[i] + b[j] > target) { j--; // 小伙伴不斷換更輕的右側砝碼，直到總重量不超標}if (a[i] + b[j] == target) { // 天平平衡，找到解！return {i, j};}// 若總和太輕，你主動換下一個更重的砝碼（i++），小伙伴保持當前位置}
}💡 為什么這個策略高效？
避免重復嘗試：一旦小伙伴調整到某個右側砝碼?
B[j]，后續你更換更重的左側砝碼時，小伙伴只需從上一次的位置繼續向左調整，無需從頭開始（時間復雜度僅為?O(n + m)）。利用有序性：砝碼盒的排列順序（升序/降序）天然引導指針移動方向，類似“夾逼”逐漸逼近目標。
這個類比將抽象的算法轉化為具體的合作場景，生動展現了雙指針如何通過“一增一減”的協同策略高效解決問題。
例四
【acwing 2816. 判斷子序列】
問題描述
給定一個長度為 n 的整數序列 a1,a2,…,
以及一個長度為 m 的整數序列 b1,b2,…,
。
請你判斷 a 序列是否為 b 序列的子序列。
子序列指序列的一部分項按原有次序排列而得的序列，例如序列 {a1,a3,a5} 是序列 {a1,a2,a3,a4,a5} 的一個子序列。
輸入格式
第一行包含兩個整數 n,m。
第二行包含 n 個整數，表示 a1,a2,…,an。
第三行包含 m 個整數，表示 b1,b2,…,bm。
輸出格式
如果 a 序列是 b 序列的子序列，輸出一行 Yes。
否則，輸出 No。
數據范圍
1≤n≤m≤1e5
?1e9≤≤1e9
輸入樣例：
3 5
1 3 5
1 2 3 4 5輸出樣例：
Yes
#include<iostream>
using namespace std;// 定義常量N為100010，用于限定數組的最大大小
const int N = 100000 + 10;
int a[N], b[N]; // 定義兩個整型數組a和b，用于存儲輸入的數據int main()
{// n表示數組a的長度，m表示數組b的長度int n, m;// 從標準輸入讀取n和m的值scanf("%d%d", &n, &m);// 循環讀入數組a的n個元素for(int i = 0; i < n; i++) scanf("%d",&a[i]);// 循環讀入數組b的m個元素for(int i = 0; i < m; i++) scanf("%d",&b[i]);// 初始化兩個索引i和j分別為0，分別用于遍歷數組a和bint i = 0, j = 0;// 當數組a沒有完全匹配完（i<n）且數組b沒有被完全掃描過（j<m），繼續循環while(i < n && j < m){// 如果當前數組a的元素a[i]與數組b的元素b[j]相等，則說明找到了一個匹配if(a[i] == b[j]){// 移動數組a的指針i到下一個位置，繼續尋找下一個匹配i++;}// 不管是否找到匹配，都需要移動數組b的指針j到下一個位置，繼續掃描j++;}// 如果數組a的所有元素都被成功匹配了（即i==n），則輸出"Yes"if(i == n) puts("Yes");// 否則，如果數組a中有任何元素未被匹配，則輸出"No"else puts("No");return 0;
}通俗比喻
想象你在玩一個“按順序找字母”的游戲：
你手上有張字母卡?
a = [A, B, C]，需要在另一張長紙條?b?上按順序找到這些字母，順序不能亂，但中間可以有其他字母。你從紙條的開頭開始找：
找到?
A?后，打勾，繼續往后找?B。如果中途遇到其他字母（比如?
X），直接跳過，繼續往后找。如果紙條找完了還沒找齊所有字母，游戲失敗；否則成功。
這段代碼就是實現這個游戲的過程。
例五、
【acwing 32. 調整數組順序使奇數位于偶數前面】
問題描述
輸入一個整數數組，實現一個函數來調整該數組中數字的順序。 使得所有的奇數位于數組的前半部分，所有的偶數位于數組的后半部分。
樣例
輸入：1 2 3 4 5
輸出:? ?1 3 5 2 4
法一、雙指針算法?
不過需要注意的是，雖然這種方法能確保奇數在前、偶數在后，但它并不保證相同類型元素之間的相對順序不變。
#include <vector>
#include<iostream>
using namespace std;class Solution {
public:// 定義resort函數，用于重新排序數組，使得所有奇數排在前面，偶數排在后面void resort(vector<int>& array) {int i = 0, j = 0; // 初始化兩個指針i和j都指向數組的起始位置// 遍歷整個數組while (j < array.size()) {// 如果array[j]是奇數，則將其與array[i]交換，并增加iif (array[j] % 2 == 1) { // 檢查當前元素是否為奇數swap(array[i], array[j]); // 交換array[i]和array[j]i++; // 移動i指針，指向下一個應該放置奇數的位置}// 無論是否執行了交換操作，都要增加j，繼續檢查下一個元素j++;}}
};int main(){Solution solve; // 創建Solution類的一個實例vector<int> arr; // 定義一個整型向量arr用于存儲輸入數據int mid; // 定義一個變量mid用于臨時存儲從標準輸入讀取的數據// 循環讀取輸入直到文件結束（EOF）while(cin >> mid) {arr.push_back(mid); // 將讀取的值添加到arr向量中}solve.resort(arr); // 調用resort函數對數組進行重新排序// 輸出重新排序后的數組for(int num : arr) {cout << num << " "; // 打印每個元素，后面跟一個空格}return 0; // 程序正常退出
}
?法二、分治+歸并
了解vector的insert用法：介紹C++vector的insert函數用法-CSDN博客
這種方法的優點在于它簡單直接，能夠保證奇數和偶數各自內部的原始順序不變，即實現了穩定的排序。不過，它的缺點是需要額外的空間來存儲奇數和偶數，因此空間復雜度為O(n)，n是數組的長度。如果內存限制嚴格，可能需要考慮其他不使用額外空間的方法。
#include <vector>
#include<iostream>
using namespace std;class Solution {
public:// 定義resort函數，用于重新排序數組，使得所有奇數排在前面，偶數排在后面void resort(vector<int>& array) {vector<int> odd, even; // 創建兩個新的向量odd和even，分別用于存儲奇數和偶數// 遍歷整個輸入數組for(int num : array) {if(num % 2 == 1) { // 如果當前數字是奇數odd.push_back(num); // 將其添加到odd向量中} else { // 如果當前數字是偶數even.push_back(num); // 將其添加到even向量中}}// 合并結果：先放奇數，再放偶數odd.insert(odd.end(), even.begin(), even.end()); // 將even向量的所有元素添加到odd向量的末尾array = odd; // 更新原數組為合并后的結果}
};int main(){Solution solve; // 創建Solution類的一個實例vector<int> arr; // 定義一個整型向量arr用于存儲輸入數據int mid; // 定義一個變量mid用于臨時存儲從標準輸入讀取的數據// 循環讀取輸入直到文件結束（EOF）while(cin >> mid) {arr.push_back(mid); // 將讀取的值添加到arr向量中}solve.resort(arr); // 調用resort函數對數組進行重新排序// 輸出重新排序后的數組for(int num : arr) {cout << num << " "; // 打印每個元素，后面跟一個空格}return 0; // 程序正常退出
}
?
)
