javaee论坛

普通会员

225648

帖子

345

回复

359

积分

楼主
发表于 2019-11-03 06:36:20 | 查看: 123 | 回复: 0

尺取法:尺取法是一种解决问题的一种技巧。这种技巧原理就是双指针的使用,所谓双指针就是两个箭头,分别指向前面和后面。而尺取法通过双指针不断推移区间的开头和结尾的一种方法。——很常用。(像在这样求区间的最值问题都能用到,此外快排也使用了双指针)

tips:此处的区间是前指针与后指针夹着的区间,并非数组。

一、问题描述:给定长度为n的数列整数a0a1……以及整数S。求出总和不小于(>=)S的连续子序列的长度的最小值。如果解不存在,则输出0。

样例输入——1:

n=10S=15a={5,1,3,5,10,7,4,9,2,8}

样例输出——1:

2(5+10)

样例输入——2:

n=5S=11a={1,2,3,4,5}

样例输出——2:

3(3+4+5)

二、代码:

voidsolve(){intres=n+1;ints=0,t=0,sum=0;//初始化双指针的开始位置以及sum的值while(1){while(t<n&&sum<S){sum+=a[t++];//后指针推移}if(sum<S)break;//遍历到最后区间sum还没有S大,则跳出循环res=min(res,t-s);sum-=a[s++];//前指针推移}if(res>n)res=0;printf("%d\n",res);}

您需要登录后才可以回帖 登录 | 立即注册

触屏版| 电脑版

技术支持 历史网 V2.0 © 2016-2017