//瞎写的
尺取法：通过保存一组下标，根据条件交替挪动以求最终解。
一般用于求取有一定限制的区间个数或最短的区间，有时能把一些枚举问题从O(nlogn)（二分）优化到O(n)。
例题：
Subsequence POJ3061
题意：给定长度为n的都是正整数的数列以及整数S。求出总和不小于S的连续子序列的长度的最小值，不存在则输出0。
思路：先记录下标b1=1，找到最小的下标b2使得b1->b2的子序列总和不小于S（不存在则输出0）并记录长度。然后将b1增加一，重复前一个过程寻找新的最小b2并计算长度，与原长度比较记录最小值。
分析，在重复过程中我们不难发现，(b1+1)->b2序列的总和必定小于S，故我们没有必要重新枚举(b1+2)->b2的点，可以保证新的下标b2大于原先的b2。
思路代码表现：
void solve() { int l=1,r=n,ans=n+1,sum=0; while(1) { while(r<=n&&sum<S)sum+=a[r++]; if(sum<S)break; ans=min(ans,r-l);//r在递归时会到最小情况+1的位置 sum-=a[l++]; } if(ans>n)ans=0; cout<<ans<<endl; }
Jessica‘s Reading Problem POJ3320
题意：给定长度为n的数列，数列值可能有重复。求出现过所有元素值的子序列的最小长度。
思路：其实相同，只是判断的条件变成了所有元素是否都出现过。
思路代码表现：
void solve() { int l=1,r=n,cnt=0,ans=n+1; map<int,int>mp; while(1) { while(r<=n&&sum<n) { if(!mp[a[r++]]) { mp[a[r++]]++; cnt++; } } if(cnt<n)break; ans=min(ans,r-l); if(mp[a[l++]]==1) { mp[a[l++]]--; cnt--; } } cout<<ans<<endl; }
//水了一篇
原文：https://www.cnblogs.com/Geospiza/p/14872593.html