双指针算法详解（含力扣和蓝桥杯例题）

目录

一、双指针算法核心概念

二、常用的双指针类型：

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