双指针——尺取法
定义：
尺取法，又称双指针法（此指针非彼指针）。双指针顾名思义，有两个“指针”，根据实际情况不断地移动，从而推进区间的左右端点以得出答案
适用性：
适用于移动方向确定(一般是从头到尾)、连续区间的最小或最大问题
板子
int r = 1, l = 1;//确定两个指针的初始位置
while(l <= n){//确定循环结束条件
while(){//括号中填右指针移动的条件
r++;//移动右指针，并更新数值
}
if(){//根据题意确定更新答案的条件
//更新答案
}
l++;//移动左指针
} 例题：
题意：
从一个序列中找出连续且和大于等于m的最小子序列，输出其长度
思路：
根据题意，提取信息：连续，大于等于m，最小
符合上面我写的双指针的使用条件
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 150000 + 5
typedef long long ll ;
//不开longlong见祖宗！
int tr[MAX];
int main()
{
int t, n, m;
cin>>t;
while (t--) {
cin>>n>>m;
for(int i = 1; i <= n; ++i){
cin>>tr[i];
}
//数组从1开始有数，所以l，r赋初值为1，sum用来计算子序列的和，minx用来更新最小长度
int l = 1, r = 1, sum = 0, minx = 1e9;
while (l <= n) {
//结束条件是左指针移除序列
while (sum < m && r <= n) {
//右指针移动的条件是：子序列和小于m且右指针还没有到达n，也就是可以继续右移
sum += tr[r++];//更新sum值与r值
}
if(sum >= m)
//更新答案的条件是：sum大于等于m
minx = min(minx, r - l);
sum -= tr[l++];
//移动左指针，并更改sum值
}
if(minx == 1e9)
cout<<0<<endl;
else
cout<<minx<<endl;
}
return 0;
} 字符串
题意：
有一个字符串S，问S的所有合法子串中，包含26个小写英文字符的最短子串的长度是多少
思路：
关键词：子串 （=连续），26个字母，最短
满足尺取法
我们可以用map来存字母和他的数量
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 150000 + 5
typedef long long ll ;
//不开longlong见祖宗！
map<char, int>mp;
int main()
{
string s;
cin>>s;
//字符串是从0开始，所以r和l都从0开始，
int l = 0, r = 0, ans = 1e9, res = 1e9;
while (r < s.size()) {
//循环结束的条件是r出字符串了
mp[s[r++]]++;
//把r处的字符塞进map里，并让他数量++
if(mp.size() == 26)
//这里是为了特判，如果输入只有26个字母的时候，下面的循环就不会进行，所以我们得特判一下子
res = r - l;
while(mp[s[l]] > 1 && mp.size() == 26){
//左指针移动的条件是目前两指针截得的字符串包含了26个字母，也就是map的大小是26，且左指针在这里面出现了不止1次，此时就可以删掉他，更新答案
mp[s[l]]--;//删掉他
ans = min(ans, r - l - 1);//更新答案
l++;//移动左指针
}
}
if(ans == 1e9)
cout<<res<<endl;
else
cout<<ans<<endl;
return 0;
} 丢手绢
题意：
小盆友围成一圈，已知每个小朋友之间的间隔，定义小朋友之间的距离为沿圆圈顺时针或逆时针走的最近距离，问离的最远的两个小朋友之间的距离
总的来说，题问的是：大于一半周长的最小间距，或者是小于一半周长的最大间距
思路：
同样是双指针，不过这次是环状，所以对于右指针要对n取模，以防超过n以后都是0，同样的因为取模，所以我们要从0开始输入，因为n%n=0
（但是我发现我第一遍交的时候左指针右指针都从1开始，然后循环结束写的是l<=n，也过了哎）
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 150000 + 5
typedef long long ll ;
//不开longlong见祖宗！
int tr[MAX];
int main()
{
int n, sum = 0;
cin>>n;
for(int i = 0; i < n; ++i ){
cin>>tr[i];
sum += tr[i];//计算间距和
}
//确定左指针右指针的初始值
int l = 0, r = 0, ans = 0, maxn = -1e9;
while (l < n) {
while (ans < sum / 2) {
ans += tr[(r++) % n];//要取模！
}
maxn = max(maxn, min(ans, sum - ans));
//更新最大值
ans -= tr[l++];
//移动左指针，并改变ans值
}
cout<<maxn<<endl;
return 0;
} 
查看26道真题和解析
