一、介绍双指针算法
双指针（或称为双索引）算法是一种高效的算法技巧，常用于处理数组或链表等线性数据结构。它通过使用两个指针来遍历数据，从而减少时间复杂度，避免使用嵌套循环。双指针算法在解决诸如查找、排序、去重等问题时非常有效。
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(n²) 降低到 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(n²) 高效得多
空数组处理：
当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]过大，需要减小j
j--;
}
if (a[i] + b[j] == target) return {i, j}; // 如果找到符合条件的数对，返回索引对(i, j)
}
return {}; // 根据题意，这里不会执行，因为保证有唯一解
}
};
int main() {
Solution ans; // 创建Solution类的对象ans
cin >> n >> m >> target; // 输入数组a的长度n，数组b的长度m，以及目标值target
for (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和b
int 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]交换，并增加i
if (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; // 程序正常退出
}
