训练（training）

解题思路

所有a[i]非负，可用滑动窗口。右端right逐步扩张并加上a[right]；只要窗口和≥S，就记录长度，再移走左端并让left前进，尽量缩短当前窗口。

不断缩短到和<S后继续扩张。若整个过程从未达标，输出-1。

正确性说明

对固定右端，左端不断右移会使窗口和不增加，因此可以持续缩短到首次失效，其前一步就是该右端的最短合法窗口。所有右端均被检查；非负性也保证被移除的左端不会在未来产生更短而遗漏的答案。取所有合法窗口最小长度即全局最优。

易错点

0不破坏非负单调性；S达10^18，窗口和用long long；不能用严格>替代≥。

复杂度

时间O(n)，空间O(n)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long S;
    cin >> n >> S;
    vector<long long> a(n);
    for (auto &x : a)
        cin >> x;
    int left = 0, best = n + 1;
    long long sum = 0;
    for (int right = 0; right < n; right++) {
        sum += a[right];
        while (left <= right && sum >= S) {
            best = min(best, right - left + 1);
            sum -= a[left++];
        }
    }
    cout << (best == n + 1 ? -1 : best) << "\n";
    return 0;
}