尺取法:
代码模板
int sum = p[1];
while (sum < y && end < x) {
end++; //注意这两个的位置,end在前可义防止end=x的同时sum>=y; 当end在前当end=x-1
sum += p[end]; //end++;之后end变成了x;此时sum也加上了p[x];此时必定会跳出循环,但是
} //可以确定的是后面只需要考虑sum大小,if(sum < y) 一定没有结果;else 有结
果,好处是不用考虑end情况;
if (sum < y) {
len = -1;
printf("0\n");
}
else {
while (1) {
if (len > end - star)len = end - star;
while (sum >= y && star <= end) {
star++;
sum -= p[star];
}
if (sum < y)
if (len > end - star + 1) len = end - star + 1;
while (sum < y && end <= x) {
end++;
sum += p[end];
}
if (end <= x)
if (len > end - star + 1) len = end - star + 1;
if (end > x) {
printf("%d\n", len);
break;
}
}
}