本文主要是介绍尺取法知识点讲解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、固定长度的情况：
最小和(sum)
输入N个数的数列，所有相邻的M个数的和共有N-M+1个，求其中的最小值。
输入格式
第1行，2个整数N，M，范围在[3…100000]，N>M。
第2行，有N个正整数，范围在[1…1000]。
输出格式
1个数，表示最小和。
输入/输出例子1
输入：
6 3
10 4 1 5 5 2
输出：
10
【方法一】：枚举开始点，计算连续M个数的和，求出最小值。
程序如下：
#include<bits/stdc++.h>
using namespace std;
long long n,m,a[100005],mins=0x7f7f7f7f7f7f7f7f;
int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n-m+1;i++){long long s=a[i];for(int j=i+1;j<=i+m-1;j++)s+=a[j];mins=min(s,mins);}cout<<mins;return 0;
}时间复杂度是o（n*m）如果数据量太大会超时。
如图1所示，如果以第一个数开始计算也就是图1红色部分。
s1=a[1]+a[2]+a[3]
如图2所示，如果以第二个数开始计算也就是图2蓝色部分
s2=a[2]+a[3]+a[4]
对比图1和图2，公式s1和s2，我们会发现，如果以第一个数开始枚举m=3个数的和，和以第二个数开始枚举m个数的和，重复了a[2]+a[3]，也就是说，我们第一个数开始枚举完m个数的和后，完全不用从第二个数再重新枚举，只要在s1的基础上保留重复部分a[2]+a[3]，去掉左边的a[1]，加入右边的a[4]，让长度保持m个。
s1=a[1]+a[2]+a[3]
s2=s1-a[1]+a[4]
尺取法：就如尺子一样，利用两个指针L和R，L代表左边枚举开始点，,R代表枚举结束点，s代表区间L到R的和，如果此时L到R刚好m个数，也就是R-L+1==m，那么找到一个长度为m的和，后面只要把s=s-a[L]+a[R+1]，L++，R++，让其长度保持为m。
【程序如下】：
#include<bits/stdc++.h>
using namespace std;
long long n,m,s,a[100005],mins=0x7f7f7f7f7f7f7f7f;
int main(){cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int L=1,R=1;R<=n;R++){s+=a[R];if(R-L+1==m){mins=min(mins,s);s=s-a[L];L++;}}cout<<mins;return 0;
}二、不固定长度情况
【程序如下】：
#include<bits/stdc++.h>
using namespace std;
long long n,m,s,a[100005];
int main(){cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];int minL=n+1;for(int L=1,R=1;R<=n;R++){s+=a[R];while(s>=m){minL=min(minL,R-L+1);s=s-a[L];L++;}}cout<<minL;return 0;
}三、总结
尺取法是一种线性算法，也是一种高效的枚举区间的方法。
记 (l,r)两个端点为一个序列内以l为起点的最短合法区间，如果r随l的增大而增大的话，我们就可以使用尺取法。
具体的做法是：
1.初始化左右端点
2.不断扩大右端点，直到满足条件
3.如果第二步中无法满足条件，则终止，否则更新结果
4.将左端点扩大1，然后回到第二步
因为r随 l增大而增大，所以 r只有 n次变化的机会，所以时间复杂度为O(n)。
这篇关于尺取法知识点讲解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
