双指针（Sliding Window / Two Pointers）

对于给定序列，由于 ，区间和函数 关于 单调递增，关于 单调递减。这意味着：

  • 当 时，必须右移右指针 以增加和。
  • 当 时，当前 是以 为起点的可行解，尝试右移左指针 以寻找更短的潜在解。

最优性证明

双指针算法能够在一次线性扫描中覆盖所有“极小可行区间”（即满足条件且减小 或增加 都会破坏条件的区间）。由于目标是最短区间且 最小，我们只需要在找到满足条件的区间时，记录并对比其长度。

复杂度分析

  • 时间复杂度：
  • 空间复杂度：

代码实现

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, x;
    cin >> n >> x;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    int l = 0;
    int r = 0;
    int cur = 0;
    int minLen = n;
    int best_l, best_r;

    while (r < n) {
        cur += a[r];
        while (l <= r && cur >= x) {
            int curLen = r - l + 1;
            if (curLen < minLen) {
                minLen = curLen;
                best_l = l;
                best_r = r;
            }
            cur -= a[l];
            l++;
        }
        r++;
    }

    best_l++;
    best_r++;

    cout << best_l << " " << best_r << endl;
}