- 👑专栏内容:算法学习随笔
- ⛪个人主页:子夜的星的主页
- 💕座右铭:日拱一卒,功不唐捐
一、前言
双指针法又称尺取法,顾名思义,在区间操作时,使用两个指针同时遍历区间,从而实现高效操作。两个指针,就像是一男一女,他们遍历区间的过程,又何尝不像是一对男女彼此追求爱情的过程呢?
接下来一起学习双指针的恋爱过程。
二、左右指针(双向奔赴)
我渴望能见你一面,但请你记得,我不会开口见你。这不是因为我骄傲,你知道我在你面前毫无骄傲可言,而是因为,唯有你也想见我的时候,我们见面才有意义。——《越洋情书》西蒙·波伏娃
1、定义
左右指针,顾名思义,指针i与指针j
,一个在左边,一个在右边。
两个指针的遍历方向相反,一个指针i
从左往右,一个指针j
从右往左。最终它们会在中间相会。
左右指针认为:真正的爱是双向奔赴,不论双方的差距有多大,距离有多远,只要双向奔赴,最终必将走到一起 ~
2、回文检查
【题目描述】 给定一个长度为 n
的字符串 S
。请你判断字符串S
是否回文。
【输出描述】 输入仅1行包含一个字符串S。
1
≤
S
≤
1
0
6
1≤ S≤10^6
1≤S≤106,保证S只包含大小写、字母。
【输出描述】 若字符串S
为回文串,则输出 Y
,否则输出 N
。
【参考样例】 输入:abcba
输出:Y
回文:正读和倒读意义相同的,称为“回文”
#include <iostream>
using namespace std;
int main()
{
string s;
cin >> s; //(1)读取字符
size_t n = s.size(); //(2)获取字符长度
int i = 0; int j = n - 1; //(3)双指针(一左一右)
while (i < j)
{
if (s[i] != s[j]) //(4)判断回文
{
cout << "N";
return 0; //(5)结束程序
}
i++; j--; //(6)移动指针
}
cout << "Y";
return 0;
}
这道题不难,有很多种方法。但是双指针是用起来最爽的。通过这道题,我们也可以大致看出来这双向奔赴的爱情大致的模样。
int i = 0;int j =n - 1;
while (i < j)
{
check(i, j); //检查题目条件
i++; j--; //移动指针,i从头到尾,j从尾到头
}
三、快慢指针(你追我赶)
不要追求幸福,而要幸福地追求。过程中的享受与快乐才是我们的需求。
1、定义
快慢指针,顾名思义,指针i与指针j
,在同一方向,但是指针i
和指针j
的遍历速度不一样。恰恰是因为i
和j
的速度不同,它们之间会产生一个大小可变的滑动窗口
,而这个窗口
,正是它们幸福的来源。
快慢指针认为:真正的爱恰恰是你追我赶时产生的窗口期,如果没有这种不断追赶的过程,爱将会变的无趣,这个就是爱的魅力 ~
2、美丽的区间
【题目描述】 给定一个长度为
n
n
n的序列
a
1
,
a
2
,
⋅
⋅
,
a
n
a_1,a_2,··,a_n
a1,a2,⋅⋅,an和一个常数 S。对于一个连续区间如果它的区间和大于或等于 S ,则称它为美丽的区间。对于一个美丽的区间,如果其区间长度越短,它就越美丽。请你从序列中找出最美丽的区间。
【输入描述】 第一行包含两个整数,S,其含义如题所述。接下来一行包含几个整数,分别表示
a
1
,
a
2
,
⋅
⋅
,
a
n
a_1,a_2,··,a_n
a1,a2,⋅⋅,an 。
10
≤
N
≤
1
0
5
,
1
≤
a
i
≤
1
0
4
,
1
≤
S
≤
1
0
8
10≤N≤10^5,1≤a_i≤10^4,1≤S≤10^8
10≤N≤105,1≤ai≤104,1≤S≤108。
【输出描述】 输出共一行,包含一个整数,表示最美丽的区间的长度。若不存在任何美丽的区间,则输出 0 。
【参考样例】
输入:
5 6
1 2 3 4 5
输出:
2
#include <iostream>
#include<algorithm>
using namespace std;
int a[101000];
int main()
{
int n, s;
cin >> n >> s;
for (int i = 0; i < n; i++)
cin >> a[i];
int sum = 0, ans = 1e8;
int i = 0, j = 0;
while (i < n) //遍历整个列表
{
if (sum < s) //若区间和小于s
{
sum += a[i]; //区间和一直加
i++; //i指针右移
}
else
{
ans = min(i - j, ans); //记录短的区间长度
sum -= a[j]; //区间和减
j++; //j指针右移
}
}
if (ans == 1e8) //答案不存在
cout << 0;
else
cout << ans;
return 0;
}
四、后记
1、当出现有序数组或者题目具有单调性(任意一个指针的增加,条件满足与否只会出现对或错这两种情况)时,应该优先想到使用左右指针来减少遍历的时间。
2、当出现前缀和、区间的时候,可以想到使用快慢指针。
注意:篇幅有限,本文只是介绍了双指针最基础的定义和最简单的题目,双指针很多题远比本文出现的题目难。大家可以点个关注,等有时间我再继续更。文章来源:https://www.toymoban.com/news/detail-817536.html
📢📢📢📢📢📢
💗 你正在阅读 【子夜的星】 的 算法笔记
👍 阅读完毕,可以点点小手赞一下
🌻 发现错误,直接评论区中帮我指正吧文章来源地址https://www.toymoban.com/news/detail-817536.html
到了这里,关于【经典算法】双指针(尺取法):爱,是双向奔赴,还是你追我赶?的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!