题目描述
A sequence of N positive integers (10 < N < 100 000), each of them less than or equal 10000, and a positive integer S (S < 100 000 000) are given. Write a program to find the minimal length of the subsequence of consecutive elements of the sequence, the sum of which is greater than or equal to S.
样例
Sample Input
2
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5
Sample Output
2
3
算法1
(双指针) $O(n)$
Python 代码
用双指针$i,j$维护区间,当区间和小于$s,j\++$,当区间和大于等于$s$记录当前长度$j-i$,再$i\++$至区间和小于$s$,记录更短长度$j-i$,再次$j\++$重复操作至序列尾部;若无法$j\++$至区间和大于等于$s$,则跳出循环,输出$0$。
t=int(input())
for i in range(t):
n,s=map(int,input().split())
a=list(map(int,input().split()))
i=0
j=0
suma=0
ans=float('INF')
while True:
while j<n and suma<s:
suma+=a[j]
j+=1
if suma<s:
break
ans=min(ans,j-i)
suma-=a[i]
i+=1
if ans>n:
ans=0
print(ans)
用双指针$i,j$维护区间,当区间和小于$s,j\++$,当区间和大于等于$s$记录当前长度$j-i+1$,再$i\++$至区间和小于$s$,记录更短长度$j-i+2$,再次$j\++$重复操作至序列尾部。
t=int(input())
for i in range(t):
n,s=map(int,input().split())
a=list(map(int,input().split()))
i=0
j=0
suma=a[0]
ans=float('INF')
while i<n-1 and j<n-1:
while j<n-1 and suma<s:
j+=1
suma+=a[j]
if suma>=s:
ans=min(ans,j-i+1)
while i<n and suma>=s:
suma-=a[i]
i+=1
if suma<s:
ans=min(ans,j-i+2)
if ans!=float('INF'):
print(ans)
else:
print(0)
C++ 代码
#include <iostream>
using namespace std;
const int N = 100000;
int a[N];
int main(){
int t;
cin>>t;
for (int k = 0; k < t; k ++ ){
int n,s;
cin>>n>>s;
for (int i = 0; i < n; i ++ )cin>>a[i];
int i=0,j=0,suma=a[0];
int ans=n+1;
while(i<n-1 &&j<n-1){
while(j<n-1 && suma<s)j++,suma+=a[j];
if(suma>=s){
ans=min(ans,j-i+1);
while(i<n && suma>=s) suma-=a[i],i++;
if(suma<s)ans=min(ans,j-i+2);
}
}
if(ans!=n+1)printf("%d\n",ans);
else printf("%d\n",0);
}
return 0;
}