子序列

链接

题目会给出一串数字,我们需要对这些连续数字进行相加,直到其大于或等于给出的值,我们需要找到最短的连续数字

比如 s=15

3 4 5 6 7 8 9 显然最短的连续数字长度为2,7 8或者8 9

这题和滑动窗口很像,应该说就是滑动窗口(不定长)?

using namespace std;
#include<vector>
#define ll long long

int main() {
    int T;
    cin >> T;
    while (T--) {
        int N;
        ll S;
        cin >> N >> S;
        vector<ll> num(N);
        for (int i = 0; i < N; i++) cin >> num[i];

        int left = 0, minLen = N + 1;
        ll sum = 0;

        for (int right = 0; right < N; right++) {
            sum += num[right];
            while (sum >= S) {
                minLen = min(minLen, right - left + 1);
                sum -= num[left];
                left++;
            }
        }

        if (minLen == N + 1) cout << 0 << endl;
        else cout << minLen << endl;
    }
    return 0;
}

时间复杂度:O(n)

空间复杂度:O(n)