图片标题

尺取法(双指针)
使用前缀和减少求连续区间和的复杂度
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <map>
#include <string>
#include <set>
#include <stack>
#include <queue>
using namespace std;
#define forseach(i,j,n) for(int i=j;i<n;i++)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define PI acos(-1)
typedef long long ll;
const int maxn = 1e5+10;

int ori[maxn];
int main()
{
	//debug;
	ios;
	int T,N,S;
	cin>>T;
	while(T--)
	{
		cin>>N>>S;
		for(int i=1;i<=N;i++)
		{
			cin>>ori[i];
                        //前缀和
			ori[i]+=ori[i-1];
		}
		if(ori[N]<S)
		{
			cout<<"0"<<'\n';
			continue;
		}
		int bg=1,ed=1,len=N;
		while(ed<=N)
		{
			int sum=ori[ed]-ori[bg-1];
            //如果长度短,更新长度
			if(sum>=S&&len>ed-bg+1)
			{
				len=ed-bg+1;
			}
            //和小于S ed后移
			if(sum<S)
				ed++;
            //和大于s且bg在ed前 bg后移
			else if(sum>=S&&bg<ed)
				bg++;
            //bg和ed在同一个位置且这个值大于S 都后移
			else
			{
				bg++;
				ed++;
			}
		}
		cout<<len<<'\n';
	}
	return 0;
}