日常无聊摸鱼就写一下题解吧

题意：给一个长度为n的正整数序列和一个正整数s，现在要求一个子区间，使得子区间的和不小于s，求该区间长度最短是多少。

思路一：暴力
O(n^2)枚举起点和终点，然后O(n)计算区间和。三个for是相互关联的，满足乘法原理，所以总复杂度O(n^3)

思路二：前缀和优化
提前预处理出来前缀和，这样我们可以O(1)计算任何一个子区间的和。复杂度由思路一的O(n^3)降低为O(n^2)

思路三：尺取(我更喜欢叫双指针 当然不是c语言的那个指针)
双指针说是一种算法，倒不如可以理解为是一种处理技巧。
因为所有数都是正整数，越加肯定是越大的。
那么我们固定左指针l不动，移动右指针r，直到找到第一个区间和≥s，然后我们右指针就没必要在动了。为什么？已经说了是正整数序列，越加肯定越大，但我们要求的是区间长度小，那么这时候我们把左指针l右移动1位，也就是从当前总和sum-a[l],l++。
然后看sum是否≥s，是的话，显然区间更短更优秀，更新答案。如果不是呢？那么继续右指针r右移这样操作。
复杂度？l最多右移n次，r最多右移n次，这两个都是独立不相关的，操作次数满足加法原理，也就是一共移动的操作次数为2n，所以复杂度是O(n)
当需要查询所有子区间的某一个相关值的时候，双指针是个很好的处理方法。

#include<iostream>
#include<algorithm>
using namespace std;
int a[1<<17];
int main(){
    int t,n,s;cin>>t;
    while(t--){
        cin>>n>>s;
        for(int i=1;i<=n;i++) cin>>a[i];
        int l=1,r=1,ans=1e9,sum=0;
        while(l<=n){
            while(r<=n && sum<s){//右指针还能右移，当前和＜s
                sum+=a[r++];
            }
            if(sum>=s) ans=min(ans,r-l);//满足和的要求，更新区间长度
            sum-=a[l++];//左指针右移
        }
        if(ans==1e9) ans=0;
        cout<<ans<<endl;
    }
    return 0;
}