题解 | #dd爱框框#
dd爱框框
https://www.nowcoder.com/practice/579c04f8ae0a41cfa9ac49ae1686dd31
双指针（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;
}
每日一题@牛客网 文章被收录于专栏
牛客网每日一题
我跟你一样，找暑期实习崩溃死，找了三个多月，无数次自我怀疑，我觉得人所有的努力还不如命运的随手一笔，但是，就算不是大厂，我们都能在不同的舞台发光发亮的
查看29道真题和解析