尺取法（算法优化技巧）

问题和序列的区间有关，且需要操作两个变量，可以用两个下标（指针）i 和  j 扫描区间。

1，反向扫描，i 从头，j 从尾，在中间相遇。

例1.1（P37）

找指定和的整数对

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m;
int a[N];
int main(){cin>>n>>m;for(int i=0;i<n;i++) cin>>a[i];sort(a,a+n);int i=0,j=n-1;while(i<j){int sum=a[i]+a[j];if(sum<m) i++;if(sum>m) j--;if(sum==m){cout<<a[i]<<" "<<a[j]<<endl;i++;}}return 0;
}

例1.2

判断回文串

#include<bits/stdc++.h>
using namespace std;
int main(){int n; cin>>n;while(n--){string s; cin>>s;bool ans =true;int i=0,j=s.size()-1;while(i<j){if(s[i]!=s[j]){ans=false; break;}i++,j--;}if(ans) cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}

允许删除（或插入，本题只考虑删除）最多一个字符，判断是否能构成回文字符串。

#include<bits/stdc++.h>
using namespace std;
int main(){int n; cin>>n;bool f;while(n--){string s; cin>>s;bool ans =true;f=true;int i=0,j=s.size()-1;while(i<j&&f){if(s[i]!=s[j]&&f){f=!f;int ii=i+1,jj=j;while(ii<jj){if(s[ii]!=s[jj]) {ans=false;break;}ii++,jj--;}int i2=i,j2=j-1;while(i2<j2){if(s[i2]!=s[j2]) {ans=false;break;}i2++,j2--;}}if(f)i++,j--;}if(ans) cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}

2，同向扫描

2.1 寻找区间和

给定一个长度为 n 的数组和一个数 s ，在这个数组中找一个区间，使这个区间的数组元素之和等于 s 。输出区间的起点和终点位置。