1、算法概述
一般当我们要去枚举满足条件的权值区间，可以用双指针遍历的方法获得满足条件的区间，这是尺取法的本质（这里的权值泛指区间的属性，包括区间和、区间内数字种类等）。尺取法是一种线性算法，记(l, r)为一个序列内以l为起点的最短合法区间，如果有r随l的增大而增大，使用尺取法。具体做法就是不断枚举l，同时求出r，由于r随l增大而增大，所以r只有 n 次变化机会，所以时间复杂度为O(n)。
尺取法需要满足的条件： 区间权值大小满足随区间长度单调变化，即区间越长区间权值越小（或越大）。
尺取法的优点： 不会去枚举到一定不满足条件的区间。
2、算法模板
for(int l = 1; l <= n; ++l)
{
while(r < n && sum < s)
{
++r;
sum += arr[r];
}
if(sum >= s && r - l + 1 <= n)
{
ans = min(ans, r - 1 + 1);
}
sum -= arr[l];
}
说明： 首先枚举l，就是相当于给所有状态按左端点分类，去枚举以l为起点的第一个满足条件的区间。确定l后，++r就相当于剪枝一定不满足条件的区间，在此过程中维护区间和sum，当我们发现终于枚举到第一个满足条件的区间时，去统计一下区间长度最小值。sum -= arr[l]逻辑很关键，它利用了尺取法的单调性，sum减去后，下一轮枚举新的l，这样l和r是以新的l为起点的最接近满足条件的区间，这样省得去枚举以新l为起点，右端点为r之前得一定不满足条件得区间。
3、算法示例
1、找到指定和的整数对
- 问题描述
输入n(n <= 100000)个整数，放在数组arr中，找出其中的两个数，它们的和等于整数m（假设肯定有解）。
- 输入
21 4 5 6 13 65 32 9 23
28
- 输出
5 23
- 说明
输入第一行是n个整数，第二行是m = 28，输出5 + 23 = 28。
题解
该题有多种解法：
1）两重循环暴力枚举，复杂度为O(n^2)，超时。
2）二分法，首先对数组从小到大排序，复杂度O(nlogn)，然后从头到尾处理数组中的每个元素，在大于arr[i]的数中使用二分查找一个等于m - arr[i]的数，复杂度O(nlogn)，总复杂度仍然为O(nlogn)。
3）哈希表，分配一个哈希表，把n个数放进去，逐个检查arr中的n个数，检查m - arr[i]在哈希表中是否有值，复杂度O(n)，空间换时间，复杂度最低。
4）尺取法，首先对数组从小到大排序，然后，设置两个变量i和j，分别指向头和尾，i初值是 0，j初值是n - 1，然后让i和j逐渐向中间移动，检查arr[i] + arr[j]，如果大于m，就让j减 1，如果小于m，就让i加 1，直至arr[i] + arr[j] = m，排序复杂度O(nlogn)，检查的复杂度O(n)，合起来总复杂度O(nlogn)。
void FindSum(int *arr, int n, int m)
{
if(arr == nullptr)
{
return;
}
sort(arr, arr + n - 1); // 排序
int i = 0;
int j = n - 1;
while(i < j)
{
int sum = arr[i] + arr[j];
if(sum > m)
{
--j;
}
if(sum < m)
{
++i;
}
if(sum == m)
{
std::cout << arr[i] << " " << arr[j] << "\n";
++i;
}
}
}
说明
在这个题目中，尺取法不仅效率高，而且不需要额外的空间。把题目的条件改变一下，可以变化为类似的问题，例如：判断一个数是否为两个数的平方和。其实也能用同向扫描来做。
2、子序列
- 问题描述
有一个长度为 N 的正整数序列（10 < N < 100000），每个数字都小于等于 10000，再给定一个正整数 S（S < 100000000），试求一个连续子序列，使得该序列的数字之和大于或等于 S，并要求该子序列尽量短。
- 输入
输入多组数据，每组数据第一行为两个正整数 N 和 S，中间用空格隔开。第二行给出这个序列，每两个整数之间用空格隔开。输入文件以 EOF 结尾。当这个连续子序列不存在时输出 0。
- 输出
对于每组数据，输出一个整数，代表满足要求的最短子序列长度，每组数据输出占一行。
题解
const int N = 500007;
const int M = 510007;
const int INF = 0x3f3f3f3f;
int n = 0;
int S = 0;
int arr[N] = {0};
int Solve()
{
int res = INF;
int s = 1;
int t = 1;
int sum = 0;
while(1)
{
while(t <= n && sum < S)
{
sum += arr[t++];
}
if(sum < S)
{
break;
}
res = min(res, t - s);
sum -= arr[s++];
}
if(res == INF)
{
res = 0;
}
return res;
}
int main()
{
int t = 0;
std::cin >> t;
while(t--)
{
std::cin >> n >> S;
for(int i = 1; i <= n; ++i)
{
std::cin >> arr[i];
}
std::cout << Solve() << "\n";
}
return 0;
}