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