尺取法是一种线性算法，也是一种高效的枚举区间的方法。

记 (l,r) 两个端点为一个序列内以 l 为起点的最短合法区间，如果 r 随 l 的增大而增大的话，我们就可以使用尺取法。

具体的做法是：

1. 初始化左右端点

2. 不断扩大右端点，直到满足条件

3. 如果第二步中无法满足条件，则终止，否则更新结果

4. 将左端点扩大1，然后回到第二步

因为 r 随 l 增大而增大，所以 r 只有 n 次变化的机会，所以时间复杂度为 O(n) 。

经典例子

给定一个长度为 n 的数列 $a_1, a_2, ..., a_n$ 及整数 S ，求不小于 S 的连续子序列的和的最小值，假设解肯定存在。

input

n=10，S=15

a= {5,1,3,5,10,7,4,9,2,8}

尺取法示意图

首先，取得满足条件的最小序列，然后依次将响右移动，若 i 向左移动的过程中序列仍然满足条件，则不移动，否则将也向右移动。

在移动的过程中记录 j-i 的最小值。