目录
一、双指针算法核心概念
二、常用的双指针类型：
2.1 对撞指针
例题1：盛最多水的容器
例题2：神奇的数组
2.2 快慢指针：
例题1：移动零
例题2：美丽的区间（蓝桥OJ1372）
3.总结：
一、双指针算法核心概念
双指针算法（Two Pointers）是一种通过两个指针协同遍历数据结构的优化技巧，常用于数组、链表等线性结构的场景，通过减少循环嵌套次数将时间复杂度从O(n²)优化至O(n)（有时候也有可能是O(n³）优化至O(n²））。其核心思想是通过指针的移动规则和终止条件设计，高效解决特定问题。
二、常用的双指针类型：
（1）对撞指针
（2）快慢指针
2.1 对撞指针
指的是两个指针left和right（简写为l和r）分别指向序列的第一个元素和最后一个元素。
然后在条件为l<r（也有可能是l<=r）时，为什么
对撞指针一般用来解决有序数组或者字符串问题（常见于区间问题）：
查找有序数组中满足某些约束条件的一组元素问题：比如二分查找、数字之和等问题。
字符串反转问题：反转字符串、回文数、颠倒二进制等问题。
例题1：盛最多水的容器
11. 盛最多水的容器 - 力扣（LeetCode）
这道题需要我们明白两个点：
1.当条件相同时，长方形的长越大，面积越大
2.长方形的高由短的那一边决定
所以我们可以发现一个技巧，我们在每一个改变双指针的时候，都应该去改变高度比较短的那一边，这样我们就可以找到更长的高，也就可以找到最大的矩阵值。
代码如下：
class Solution {
public:int maxArea(vector<int>& height) {// 在同等条件下，长方形的长越大，面积越大// 长方形的高是由比较短的那一边决定的int l = 0, r = height.size() - 1;int ans = 0;while(l < r){// 遍历左指针和右指针int num = min(height[l], height[r]);ans = max(ans, num * (r - l)); // 更新面积的最大值if(height[l] <= height[r]){ // 查看是否有更大的值l++;}else{r--; }}return ans;}
};
例题2：神奇的数组
链接如下：
蓝桥账户中心
首先这道题就是需要使用对撞指针让我们逐个遍历，并使用前缀和用来后面获得每一个子区间的前缀和和异或前缀和，代码如下：
/** @Author: error: error: git config user.name & please set dead value or install git && error: git config user.email & please set dead value or install git & please set dead value or install git* @Date: 2025-03-19 08:20:27* @LastEditors: error: error: git config user.name & please set dead value or install git && error: git config user.email & please set dead value or install git & please set dead value or install git* @LastEditTime: 2025-03-19 15:18:52* @FilePath: \VSCode\神奇的数组.cpp* @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE*/
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 2e5 + 20;
ll a[N] = { 0 }, prefix[N] = { 0 }, yh[N] = { 0 }; // 定义原数组，前缀和数组以及异或前缀和数组int main() {cin.tie(nullptr);cout.tie(nullptr);ios::sync_with_stdio(0);int n;cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i]; prefix[i] = prefix[i - 1] + a[i]; // 求前缀和yh[i] = yh[i - 1] ^ a[i]; // 求异或前缀和}// 开始计算组合数ll ans = 0;for (int right = 1, left = 1; right <= n; right++) { // 定义好左指针以及右指针// 这里请注意比较运算符的优先级比算数低，所以我们计算出前缀和的时候，一定要加上括号// (prefix[right] - prefix[left - 1] != yh[right] ^ yh[left - 1])会被解析为：// ((prefix[right] - prefix[left - 1]) != yh[right]) ^ yh[left - 1]，这显然是不行的。while (left <= right && (prefix[right] - prefix[left - 1]) != (yh[right] ^ yh[left - 1])) {left++;}ans += (right - left + 1); // 如果符合要求，就添加进去}cout << ans << endl;return 0;
}2.2 快慢指针：
快慢指针简介：
快慢指针一般比对撞指针更难想，也更难写，指的是两个指针侧开始遍历序列，且移动的步长一慢一快。快的指针被称为快指针，移动慢的指针被称为慢指针。为了方便理解，我们称快指针为r，慢指针为l，这样慢指针和快指针构成区同。两个指针以不同速度、不同策略移动，直到快指针移动到数组尾端，或者两指针相交，或者满足其他特殊条件时为止。
快慢指针解题方法：
1.使用两个指针1、r。1一般指向序列第一个元素，即：1=1，r一般指向序列第零个元素（用来给子区间初始化用的），即：r=0。即初始时区间[, rl=[1，0]表示为空区间。
2.在循环体中将左右指针向右移动。当满足一定条件时，将慢指针右移，即l++。当满足另
外一定条件时（也可能不需要满足条件），将快指针右移，即r++，保持[l，r]为合法区间。
3.到指针移动到数组尾端（即l=n且r==n），或者两指针相交，或者满足其他特殊条件时跳
出循环体。
例题1：移动零
283. 移动零 - 力扣（LeetCode）
解题思路（这些思路是看网上的大神写的）：
这道题就是创建两个指针i和j，在第一次遍历的时候，我们需要让j来记录当前有多少个非0的数字，如果当前数字不是0的话，执行nums[j++] = nums[i];这样我们就可以保证当数字为0的时候，j指针停了下来，直到我们找到了又一个非0的数字为止。遍历完之后，j就是最后一个非0数字在数组上的位置。然后进行第二次遍历，让j后面的数字全部设置为0就可以了，因为非零的数字已经统计完了。
代码如下：
class Solution {public void moveZeroes(int[] nums) {if(nums==null) {return;}//第一次遍历的时候，j指针记录非0的个数，只要是非0的统统都赋给nums[j]int j = 0;for(int i=0;i<nums.length;++i) {if(nums[i]!=0) {nums[j] = nums[i];j++;}}//非0元素统计完了，剩下的都是0了//所以第二次遍历把末尾的元素都赋为0即可for(int i=j;i<nums.length;++i) {nums[i] = 0;}}
} 也可以写成这个样子，更加的简洁：
class Solution {
public:void moveZeroes(vector<int>& nums) {int slow = 0;for (int i = 0; i < nums.size(); i++) {if (nums[i] != 0) {// 每次保证是0和非0的交换swap(nums[slow++], nums[i]);}}}
};例题2：美丽的区间（蓝桥OJ1372）
蓝桥账户中心
这道题就是需要我们使用枚举+双指针的思想，我们需要在保持左指针不变的情况下，遍历不同的右指针找到最美丽的区间（也就是区间和sum大于题目所给的值s，并且区间也是最小）。并且要记得更新最小的值。
代码如下：
#include<iostream>
using namespace std;
const int N = 1e5;
int a[N];
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, s, sum = 0; // n为数组大小，s为目标值，sum为当前和cin >> n >> s;for(int i = 1; i <= n; i++){cin >> a[i];}int ans = n + 1; // 记录答案for(int r = 0, l = 1; l <= n; l++){ // 开始遍历快慢指针while(l > r || r + 1 <= n && sum < s){ // 左指针固定，右指针向右移动r++;sum += a[r]; // 右指针向右移动，增加当前和}if(sum >= s){// 如果当前的和大于等于目标值，更新答案ans = min(ans, r - l + 1);}sum -= a[l]; // 左指针向右移动，减少当前和}if(ans==n+1) cout<<0;else cout<<ans;return 0;}
3.总结：
双指针一般是由快慢指针和对撞指针这两部分组成，其中快慢指针一般是比对撞指针要难一些，我们需要通过题目的意思来设置合适的条件。然后枚举每一种情况就行。
写在最后：
我们可以在这里学习C++知识：
0voice · GitHub
