尺取法（算法优化技巧）

问题和序列的区间有关，且需要操作两个变量，可以用两个下标（指针）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 。输出区间的起点和终点位置。