题目：

给定长度为n的整数数列 $a_0,a_1,...,a_{n-1}$以及整数S,求出总和不小于S的连续自序列的长度最小值。如果不存在，则输出0

样例：

输入
n = 10
S = 15
a = {5 , 1,3 ,5 ,10,7,4,9,2,8}
输出
2 （5 ,10)

思路：

尺取法通常的是保留数组的一对下标（开始到结束），然后根据实际情况交替移动。

我们假设从i开始总和超过S的连续子序列如果为$a_i,a_{i+1}...a_{i+j}$
即

画图说明一下可能更形象，以样例输入为例子：
1.初始化的时候，开始指针和结束指针都指向第一个，此时的子序列和为$S=a_i \lt 15$

2. 向右移动结束指针，当移到10位置，第一次出现$S=a_0+a_1+a_2+a_3+a_4 \ge 15$

3.这时移动开始的指针，先向右移动一格$S=a_1+a_2+a_3+a_4 \ge 15$

4.继续移动开始的指针，当移动到10的时候,$S=a_4 \lt 15$,这时就得到一个解$(a_3,a_4)$

5,然后不断重复上面的步骤，找出最短的一个就是该问题的解

代码

#include <iostream>
using namespace std;

int main(){
    int n,S;
    cout<<"n = ";
    cin>>n;
    cout<<"S = ";
    cin>>S;
    int *a = new int[n];
    cout<<"input a[] :";
    for(int i=0;i<n;i++){
        cin>>a[i];
    }

    int b=0,e=0,sum=0,res=n+1;
    while(1){
        //移动结束的下标
        while(e < n && sum < S){
            sum+=a[e++];
        }
        if(sum < S) break;
        //移动开始的下标
        while(sum >= S){
            sum-=a[b++];
        }

        res=min(res,e-b+1);
    }
    if(res>n){
        res=0;
    }
    cout<<res<<endl;
}

运行结果

n = 5
S = 11
input a[] :1 2 3 4 5
3