Java教程

一道双指针(尺取法)的经典例题

本文主要是介绍一道双指针(尺取法)的经典例题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

现在给定一个整数s以及一个长度为n的整数数列a[0],a[1],a[2],a[3]....a[n-1] (全为正数),

请你求出总和不小于s的连续子序列的长度的最小值。如果解不存在,则输出0。

输入
第一行:两个整数,表示 s 与 n,其中1<=s<=10^9,1<=n<=500000;
第二行:n个用空格隔开的整数,表示 a[0] a[1] ... a[n-1],其中对于任意a[i]有1≤a[i]≤10^9。

输出
输出总和不小于s的连续子序列长度的最小值。
如果解不存在,则输出0。

输入样例
50 20
10 8 9 3 11 8 5 1 1 1 1 20 8 9 11 4 13 22 9 6

输出样例
4

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int s,n,i;//s是题目要求,n是长度
	int len;//初始化答案的长度
	int l=0,r=0;//双指针
	int sum=0;//题目中的总和 
	cin>>s>>n;
	int a[n];//为什么在cin>>s>>n前面写答案就是1? 
	len=n+1;
	for(i=0;i<n;i++)
	{
		cin>>a[i];
	}
	while(1)
	{
		while(l<n&&sum<s)
		{
			sum=sum+a[l++];//从左指针开始进行加法运算 
		}
		if(sum<s)	
			break;//全加起来都小于s 
		else
		{
			len=min(len,l-r);
			sum=sum-a[r++];//右指针此时还不确定,所以应该减去右指针右边的数组元素 
		}
	}
	if(len>n)//长度溢出
	{
		len=0;//重新来一次	
	} 
	printf("%d\n",len);
	return 0;
}


//本代码在cin>>s>>n之前int a[n]时,案例答案为1不为4,why?

这篇关于一道双指针(尺取法)的经典例题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!