Subsequence （尺取法）

尺取法（双指针）例题。暴力算法就是两重for循环枚举i和j的位置。这里我们可以进行优化：①当i到j的和≥s时，j就不需要往后移动了；②当i变成i+1时，由于i到j-1的和小于s，i到j的和≥s，因此i+1到j-1的和一定小于s。也就是说，当i加1时，j只需后移一位即可开始新一轮的判断。
这里从i到j的和，采用前缀和实现。注意，i到j的和是j的前缀和减去i-1的前缀和。
令a[0]=0,sum[0]=0,i从1开始循环，这样a[i-1]就不会越界。
代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100010];
ll sum[100010];//计算前缀和
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        ll n,s;
        scanf("%lld %lld",&n,&s);
        memset(a,0,sizeof(a));
        memset(sum,0,sizeof(sum));
        sum[0]=0;
        for(ll i=1;i<=n;i++){
            scanf("%lld",&a[i]);//a从下标1开始，下标0设为0，方便后续sum[j]-sum[i]
            sum[i]=sum[i-1]+a[i];
        }

        ll j=0;
        ll ans=100020;
        for(ll i=1;i<=n;i++){
            while(j<=n && sum[j]-sum[i-1]<s)    j++;//注意从i加到j，是j的前缀和减去i-1的前缀和
            if(j>n)     break;
            ans=min(ans,j-i+1);
            j--;
        }
        if(ans==100020)    printf("0\n");
        else               printf("%d\n",ans);
    }
    return 0;
}