Problem5375--Smallest Subarray with a given sum

5375: Smallest Subarray with a given sum

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

Given an array of positive numbers, which size is $N$, and a positive number $S$, find the length of the smallest contiguous subarray whose sum is greater than or equal to $S$. Return $0$ if no such subarray exists.

Input

Two lines.
The first line contains two positive numbers, $N$ $(2 \leq N \leq 2*10^5)$ and $S$ $(1 \leq S \leq 10^4)$。.
The second line contains $N$ positive numbers, $a_i$ ($1 \leq a_i \leq 10^6$).

Output

One positive number, the answer.

Sample 1 Input

6 7
2 1 5 2 3 2

Sample 1 Output

2
The smallest subarray with a sum great than or equal to $7$ is $[5, 2]$. So the answer is $2$.

Source/Category

基础算法 4.5.双指针