算法——尺取

尺取尺取，像尺子一样截取一段

有一道题如下:

一个长度为 n 的数组(全为正整数)与一个整数 m ，数组中是否有大于等于整数 m 的子序列，假如有求最短的子序列长度，否则输出-1。

此题可以用枚举法慢慢求，数组长度较小时，可以用这种简单粗暴的方法。但是数组长度过大时则会超时。
因为时间复杂度为 O(n！)。

枚举法大家都想得到所以就直接上尺取的代码
代码如下

#include<stdio.h>

int main()
{
	int n, m, i, min, sum; // min 代表最短子序列长度 
	int head, tail; // head 代表左端点，tail 代表右端点 
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		sum = 0; // 初始化sum 
		min = n+1; // 初始化min
		head = tail = 0; // 初始化 head 、tail 
		
		int a[1024] = {0};
		for(i=0 ; i<n ; i++)
			scanf("%d",&a[i]);
		 
		while(sum < m && tail < n)
		{
			sum+ = a[tail];
			tail++;
		}
		// 先计算最初大于等于m 的子序列 
		if(sum < m)
		{
			min = -1;
		}
	//假如右端点已经到达数组尾部都没有大于等于m 则令min=-1 代表没有这样的子序列 
		else
		{
			if(tail-head < min)min = tail-head; // 更新min 值 
			 
			while(tail < n)
			{
				while(sum >= m && head < tail)
				{
					sum- = a[head];
					head++;
				}
				// 保持右端点不动；左端点右移；直到sum 值小于m 或者head 超过tail 
				
				while(sum < m && tail < n)
				{
					sum+ = a[tail];
					tail++;
				}
				// 保持左端点不动；右端点右移；直到sum 值大于等于m 或者tail超过n
				
				if(sum >= m) // 假如sum 值大于等于m 更新min 值 
				{
					if(tail-head < min)min = tail-head; // 循环更新min 值 
				}
			}
		}
		printf("%d\n",min); 
	}
	return 0;
}

例如
n=10，m=15
5 1 3 6 10 7 4 9 2 8
输出
2
流程如下图

图片与例子来源于(https://www.cnblogs.com/wkfvawl/p/9016281.html ) 侵删！！！