算法练习——双指针算法(更新中)

一、介绍双指针算法

双指针（或称为双索引）算法是一种高效的算法技巧，常用于处理数组或链表等线性数据结构。它通过使用两个指针来遍历数据，从而减少时间复杂度，避免使用嵌套循环。双指针算法在解决诸如查找、排序、去重等问题时非常有效。

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]过大，需要减小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++），小伙伴保持当前位置}
}