题目描述

给定一个整数 s，求一个长度为 n 的序列中总和不小于 s 的连续子序列的最短长度，如果不存在，则输出 -1 。

输入格式

第一行两个整数 n , s ( 1 <=n < $3*{10}^5$ , 1 <= s <= ${10}^9$ )

第二行 n 个整数，( 0 <=每个整数 <= ${10}^6$ )

输出格式

一个整数，代表总和不少于 s 的连续子序列的最短长度，如果不存在满足条件的子序列，输出 -1 。

样例

10 15
5 1 3 5 10 7 4 9 2 8

2

笨方法

两层循环，第一层循环枚举子序列的开始下标，第二层循环枚举子序列的结束下标，然后算这一段序列的和是否大于等于 s （可以用上前缀和计算公式 ），如果是则刷新一下序列长度的最小值。这个程序的计算复杂度是 O($n^2)，题目说 n 最大会到 $3*{10}^5$，所以计算复杂度会是 $9*{10}^{10}$ ，一定超时的。

#include<bits/stdc++.h>
using namespace std;
int sum[300001]; //前缀和数组 
int main()
{
	int n,s,i,j,t,ans=100000000;

	scanf("%d%d",&n,&s);
	
	for(i=1;i<=n;i++)
	{
		scanf("%d",&t);
		sum[i] = sum[i-1] + t;
	}

	for(i=1;i<=n;i++)
	{
		for(j=i;j<=n;j++)
		{
			if(sum[j]-sum[i-1]>=s)
				ans = min(ans,j-i+1);
		}
	}

	printf("%d ",ans);

	return 0;
}

双指针算法

如何改进暴力枚举：

1. 假设有一段子序列，从 i 开始，到 j 结束，其和已经够了 s ，刷新了最短长度之后，其实没必要继续枚举更大的 j 了。因为，从 i 到 j+1 的子序列和会比从 i 到 j 更大，既然 i 到 j 的和就够 s 了，i 到 j+1 也肯定够。但是，题目问的是在连续子序列的和够s的前提下，最短的序列长度，所以这个长度是越短越好，从 i 到 j+1 的长度比 从 i 到 j 更大，所以改变长度的最小值。

2. 假设从 i 到 j 的子序列之和够 s ，然后第二层循环就不再枚举更大的 j（也就是说，第一点不足之处得到了改进）。这时候就要枚举更大的 i 了， j 是否需要从 i 开始枚举呢？实际上是不需要的。因为，从 i 到 j 刚好达到或者超过 s，说明了 i 到 j-1 的序列和是不够 s 的；因此从 i+1 到 j-1 的和就更不可能够 s 了。这些不可能满足条件的枚举是无效枚举，我们应该直接跳过，所以，当枚举下一个 i 的时候，j 不需要回调到 i，而是从上一轮循环的位置开始枚举。

上图就是改进之后的枚举思路，i 指针和 j 指针一直在变，我们把 i 和 j 之间的这段子序列标成灰色底色方便观察。我们就是根据灰色的这段数字的和是否达到 s 来决定如何移动 i 和 j 指针的。

1. 如果不够 s , 说明灰色的这段还不满足题意，和还不够大。为了获得更大的和，向移动 j 指针（j++）。

2. 如果和够 s ，刷新答案，不再枚举更大的 j; 枚举下一个 i （i++）

3. 当 j 超出 n 的时候可以结束循环。j 之所以从 n 的位置变成 n+1 , 是因为那个时候从 i 到 j 的和不够 s ,也就是说从 i 到 n 的和不够 s ，那从 i+1 到 n 就更不够 s 了，所以没必要继续枚举下去了。

这个算法每次循环都让 i 和 j 当中的一个增加一，所以计算复杂度是 O(n+m)

程序填空

#include<bits/stdc++.h>
using namespace std;
int sum[300001]; //前缀和数组 
int main()
{
	int n,s,i,j,t,ans=100000000,ss;

	scanf("%d%d",&n,&s);
	
	for(i=1;i<=n;i++)
	{
		scanf("%d",&t);
		sum[i] = 填空(1);
	}

	bool Found=false;
	i=j=1;
	while(i<=n&&j<=n)
	{
		ss = sum[j] - 填空(2);
		if(ss<s)
			填空(3);
		else
		{
			ans = min(ans,填空(4));
			Found = true;
			填空(5);
		}
	}
	if(Found)
		printf("%d",ans);
	else
		printf("-1"); //也可以通过 sum[n] 和 s 的比较来判断是否找不到满足条件的序列

	return 0;
}

填空(1) {{ input(1) }}

填空(2) {{ input(2) }}

填空(3) {{ input(3) }}

填空(4) {{ input(4) }}

填空(5) {{ input(5) }}