【经典算法】双指针（尺取法）：爱，是双向奔赴，还是你追我赶？

2023-07-18

int 指针区间

👑专栏内容：算法学习随笔⛪个人主页：子夜的星的主页💕座右铭：日拱一卒，功不唐捐目录一、前言二、左右指针（双向奔赴）1、定义2、回文检查三、快慢指针（你追我赶）1、定义2、美丽的区间四、后记一、前言双指针法又称尺取法，顾名思义，在区间操作时，使用两个指针同时遍历区间，从而实现高效操作。两个指针，就

👑专栏内容：算法学习随笔
⛪个人主页：子夜的星的主页
💕座右铭：日拱一卒，功不唐捐

一、前言

双指针法又称尺取法，顾名思义，在区间操作时，使用两个指针同时遍历区间，从而实现高效操作。两个指针，就像是一男一女，他们遍历区间的过程，又何尝不像是一对男女彼此追求爱情的过程呢？

接下来一起学习双指针的恋爱过程。

二、左右指针（双向奔赴）

我渴望能见你一面，但请你记得，我不会开口见你。这不是因为我骄傲，你知道我在你面前毫无骄傲可言，而是因为，唯有你也想见我的时候，我们见面才有意义。——《越洋情书》西蒙·波伏娃

1、定义

左右指针，顾名思义，指针i与指针j，一个在左边，一个在右边。
两个指针的遍历方向相反，一个指针i从左往右，一个指针j从右往左。最终它们会在中间相会。

左右指针认为：真正的爱是双向奔赴，不论双方的差距有多大，距离有多远，只要双向奔赴，最终必将走到一起 ~

2、回文检查

【题目描述】 给定一个长度为 n 的字符串 S。请你判断字符串S 是否回文。
【输出描述】 输入仅1行包含一个字符串S。 $1≤ S≤10^6$ ，保证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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

这道题不难，有很多种方法。但是双指针是用起来最爽的。通过这道题，我们也可以大致看出来这双向奔赴的爱情大致的模样。

int i = 0;int j =n - 1;
    while (i < j)             
    {   
        check(i, j);  //检查题目条件
        i++; j--;    //移动指针，i从头到尾，j从尾到头
    }
1
2
3
4
5
6

三、快慢指针（你追我赶）

不要追求幸福，而要幸福地追求。过程中的享受与快乐才是我们的需求。

1、定义

快慢指针，顾名思义，指针i与指针j，在同一方向，但是指针i和指针j的遍历速度不一样。恰恰是因为i和j的速度不同，它们之间会产生一个大小可变的滑动窗口，而这个窗口，正是它们幸福的来源。

快慢指针认为：真正的爱恰恰是你追我赶时产生的窗口期，如果没有这种不断追赶的过程，爱将会变的无趣，这个就是爱的魅力 ~

2、美丽的区间

【题目描述】 给定一个长度为 $n$ 的序列 $a_1,a_2,··,a_n$ 和一个常数 S。对于一个连续区间如果它的区间和大于或等于 S ,则称它为美丽的区间。对于一个美丽的区间，如果其区间长度越短，它就越美丽。请你从序列中找出最美丽的区间。
【输入描述】 第一行包含两个整数，S,其含义如题所述。接下来一行包含几个整数，分别表示 $a_1,a_2,··,a_n$ 。
$10≤N≤10^5,1≤a_i≤10^4,1≤S≤10^8$ 。
【输出描述】 输出共一行，包含一个整数，表示最美丽的区间的长度。若不存在任何美丽的区间，则输出 0 。
【参考样例】
输入：

输出：

2
1

#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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32