题解 | dd爱框框

问题描述

滑动窗口问题

解题思路

由于所有元素均为正数，可以使用滑动窗口（双指针）算法，时间复杂度 (O(n))：

1. 初始化左右指针 (l = 1)，窗口和 (sum = 0)，记录最短长度及对应区间。
2. 遍历右指针 (r) 从 1 到 (n)： 将 (a[r]) 加入窗口，更新 (sum)。当 (sum >= x) 时，尝试左移 (l) 缩小窗口，同时记录当前窗口的长度和位置，直到 (sum < x)。
3. 最终输出最短区间的左右端点。

复杂度分析

• 时间：(O(n))，每个元素最多进出窗口一次。
• 空间：(O(1))，仅需常数个变量。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define int long long

signed main() {
    int n, x;cin>>n>>x;
    vector<int> a(n + 1);
    for(int i = 1;i <= n;++i) cin>>a[i];
    
    queue<pair<int, int>> q;
    int sum = 0;
    int l = 0, r = 0, cnt = n + 1;
    for(int i = 1;i <= n;++i){
        sum += a[i];
        q.push({a[i],i});
        while(sum >= x && q.size() > 0){
            if(sum >= x && q.size() < cnt) {
                l = q.front().second, r = q.back().second, cnt = q.size();
            }
            sum -= q.front().first;
            q.pop();
        }
        // cout<<sum<<endl;
    }
    cout<<l<<" "<<r<<endl;
}
// 64 位输出请用 printf("%lld")