深高北-双指针
2026-06-12 17:29:57
发布于：广东
79阅读
0回复
0点赞
双指针思想笔记（C++版）
一句话理解
双指针：用两个“箭头”在数组或字符串上移动，解决需要比较、查找、反转等问题。
就像两个人同时在一条路上走，有时一起走，有时面对面走，用他们的位置关系来解决问题。
一、什么是双指针？
双指针：使用两个指针（下标）来遍历数据结构，通过移动指针来高效解决问题。
核心思想：利用两个指针的位置关系，减少循环的层数，把 O(n²) 变成 O(n)。
常见类型：
- 左右指针：一个在左，一个在右，向中间移动
- 快慢指针：一个走得快，一个走得慢
- 同向指针：两个都从左边开始，一前一后
二、左右指针（对撞指针）
题目1：两数之和（洛谷P1102）
题目描述：给定 n 个从小到大排好序的整数和一个目标数 target，请找出两个数，使它们的和等于 target。输出这两个数的下标（从1开始）。题目保证有唯一解。
输入样例：
6
1 2 4 6 8 10
8
输出样例：
2 4
（因为 a[2]=2, a[4]=6，和是8）
#include <iostream>
using namespace std;
int a[100010];
int main() {
int n, target;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
cin >> target;
int left = 1;
int right = n;
while (left < right) {
int sum = a[left] + a[right];
if (sum == target) {
cout << left << " " << right << endl;
return 0;
} else if (sum < target) {
left++;
} else {
right--;
}
}
return 0;
}
题目2：回文判断（洛谷P1015）
题目描述：给定一个字符串，判断它是否是回文串（正着读和倒着读一样）。字符串长度不超过1000。
输入样例：
abcba
输出样例：
YES
#include <iostream>
#include <string>
using namespace std;
char s[1010];
int main() {
string str;
cin >> str;
int n = str.length();
for (int i = 1; i <= n; i++) {
s[i] = str[i - 1];
}
int left = 1;
int right = n;
bool isPal = true;
while (left < right) {
if (s[left] != s[right]) {
isPal = false;
break;
}
left++;
right--;
}
if (isPal) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
return 0;
}
题目3：盛最多水的容器（洛谷P1652）
题目描述：给定 n 个非负整数 a[1], a[2], ..., a[n]，每个数代表坐标中的一个点 (i, a[i])。找出两条线，使得它们与 x 轴构成的容器能容纳最多的水，输出最大面积。
思路：左右指针，每次移动高度较小的那个指针。
输入样例：
9
1 8 6 2 5 4 8 3 7
输出样例：
49
#include <iostream>
#include <algorithm>
using namespace std;
int a[100010];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int left = 1;
int right = n;
int ans = 0;
while (left < right) {
int area = min(a[left], a[right]) * (right - left);
ans = max(ans, area);
if (a[left] < a[right]) {
left++;
} else {
right--;
}
}
cout << ans << endl;
return 0;
}
三、快慢指针
题目4：删除有序数组中的重复项（洛谷P1116）
题目描述：给定一个有序数组，删除重复出现的元素，使每个元素只出现一次，返回新数组的长度。不要使用额外数组，必须在原数组上操作。
输入样例：
8
1 1 2 2 2 3 4 4
输出样例：
4
（去重后前4个位置：1 2 3 4）
#include <iostream>
using namespace std;
int a[100010];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
if (n == 0) {
cout << 0 << endl;
return 0;
}
int slow = 1;
for (int fast = 2; fast <= n; fast++) {
if (a[fast] != a[slow]) {
slow++;
a[slow] = a[fast];
}
}
cout << slow << endl;
return 0;
}
题目5：找出数组的中间位置
题目描述：给定一个数组，找出它的中间位置。如果数组长度是奇数，输出正中间的下标；如果是偶数，输出靠左的那个中间下标。
输入样例1：
5
1 2 3 4 5
输出样例1：
3
输入样例2：
6
1 2 3 4 5 6
输出样例2：
3
#include <iostream>
using namespace std;
int a[100010];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int slow = 1;
int fast = 1;
while (fast + 1 <= n) {
slow++;
fast += 2;
}
cout << slow << endl;
return 0;
}
四、同向指针
题目6：移除元素（洛谷P1177）
题目描述：给定一个数组和一个值 val，原地移除所有数值等于 val 的元素，返回新数组的长度。元素的顺序可以改变。
输入样例：
10
1 2 3 4 5 2 6 7 2 8
2
输出样例：
7
（剩余元素：1 3 4 5 6 7 8）
#include <iostream>
using namespace std;
int a[100010];
int main() {
int n, val;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
cin >> val;
int slow = 1;
for (int fast = 1; fast <= n; fast++) {
if (a[fast] != val) {
a[slow] = a[fast];
slow++;
}
}
cout << slow - 1 << endl;
return 0;
}
题目7：把0移到末尾（洛谷P1111）
题目描述：给定一个数组，把所有的0移到数组的末尾，同时保持非零元素的相对顺序。
输入样例：
9
0 1 0 3 12 0 8 7 0
输出样例：
1 3 12 8 7 0 0 0 0
#include <iostream>
using namespace std;
int a[100010];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int slow = 1;
// 把非0元素移到前面
for (int fast = 1; fast <= n; fast++) {
if (a[fast] != 0) {
a[slow] = a[fast];
slow++;
}
}
// 后面的位置补0
for (int i = slow; i <= n; i++) {
a[i] = 0;
}
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
cout << endl;
return 0;
}
五、双指针常见题型总结
| 类型 | 指针移动方式 | 经典题目 |
|---|---|---|
| 左右指针 | 一左一右，向中间移动 | 两数之和、回文判断、盛水容器 |
| 快慢指针 | 一快一慢，快慢速度不同 | 数组去重、找中点 |
| 同向指针 | 一前一后，都向右移动 | 移除元素、移动零 |
六、时间复杂度对比
| 方法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 暴力双重循环 | O(n²) | O(1) |
| 双指针 | O(n) | O(1) |
七、易错点
| 易错点 | 正确做法 |
|---|---|
| 下标从0开始还是从1开始 | 本笔记统一从1开始 |
| 左右指针需要数组有序 | 两数之和、盛水容器需要有序 |
| 循环条件写错 | 左右指针用 left < right |
| 快慢指针边界 | 注意 fast + 1 <= n 防止越界 |
八、总结
| 要点 | 内容 |
|---|---|
| 核心思想 | 用两个指针减少循环层数 |
| 时间复杂度 | O(n) |
| 空间复杂度 | O(1) |
| 适用场景 | 数组、字符串相关问题 |
| 下标习惯 | 本笔记统一从1开始 |
记忆口诀
双指针，真神奇，两个箭头来回移
左右指针向中间，两数和与回文题
快慢指针一快慢，去重找中点搞定
同向指针一前后，移除元素移零灵
暴力循环 n 平方，双指针 n 就搞定
下标统一从1起，边界判断要仔细
T1
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m,a[100010],b[100010];
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>b[i];
sort(a+1,a+n+1);
sort(b+1,b+m+1);
int i=1,j=1,ans=0;
while(i<=n && j<=m){
if(a[i]>=b[j]){
i++;
j++;
ans++;
}else{
i++;
}
}
cout<<ans;
return 0;
}
T2
#include <bits/stdc++.h>
using namespace std;
bool cmp(char a,char b){
return a>b;
}
int main(){
string s;
cin>>s;
sort(s.begin(),s.end(),cmp);
int sl=0;
for(int ft=1;ft<s.size();ft++){
if(s[sl]!=s[ft]){
sl++;
s[sl]=s[ft];
}
}
for(int i=0;i<=sl;i++){
cout<<s[i];
}
return 0;
}
T3
#include <bits/stdc++.h>
using namespace std;
int main(){
int w,n,p[100010],b[100010];
cin>>w>>n;
for(int i=1;i<=n;i++) cin>>p[i];
sort(p+1,p+n+1);
int l=1,r=n,ans=0;
while(l<=r){
if(p[l]+p[r]<=w){
l++;
r--;
}else{
r--;
}
ans++;
}
cout<<ans;
return 0;
}
已预习
有帮助，赞一个