爱框框（滑动窗口内值加和大于x的最小区间）
文章目录
题目链接： dd爱框框_牛客网
题目描述
读入n，x，给出n个数a[1],a[2],……,a[n]，求最小的区间[l, r]，使 a[l]+a[l+1]+……+a[r] ≥ x，若存在相同长度区间，输出最小的那个
输入描述
- 第一行两个数，n(1≤n≤10000000), x(1≤x≤10000)
- 第二行n个数a[i] (1≤a[i]≤1000)
输出描述
输出符合条件l,r (保证有解)
读懂题目
注意点：
- 题中描述为 “n个数a[1],a[2],……,a[n]“、“求最小的区间[l, r]” ，而我们多数情况下无论数据存储还是区间下标表示都是从0开始，这里需要从1开始记录下标。
- 输入描述中n个数中所有值都大于0，否则优化算法（滑动窗口）不可用。
方案一（暴力–超时）
1. 利用 multimap 实现
// 利用 multiset：全部案例超时
class Less_set
{
public:
bool operator()(const pair<int, int>& a,
const pair<int, int>& b) const
{
return (a.second - a.first) <= (b.second - b.first);
}
};
int main()
{
int n = 0, x = 0;
cin >> n >> x;
vector<int> v(n, 0);
for(int i = 0; i < n; i++)
{
cin >> v[i];
}
// pair存储区间
multiset<pair<int, int>, Less_set> mt_set;
for(int i = 0; i < n; i++)
{
int sum = 0;
for(int j = i; j < n; j++)
{
sum += v[j];
if(sum >= x)
{
mt_set.insert( pair<int, int>(i, j) );
break;
}
}
}
cout << mt_set.begin()->first << " "
<< mt_set.begin()->second << endl;
提交截图：
可以看到代码逻辑没有问题，但是时间复杂度过高，无法通过全部案例。
时间复杂度分析：
使用了两层循环，外层循环遍历每个元素作为区间的起点，内层循环寻找满足条件的区间终点。
对于每个起点，最坏情况下可能需要遍历到数组的末尾，因此内层循环的时间复杂度是 O(n)。由于需要对每个起点执行内层循环，外层循环的时间复杂度也是 O(n)。
因此，总的时间复杂度是
O(n^2)
2. 利用 priority_queue 实现
// 利用 priority_queue：超时（通过率20%）
class Greater_pq
{
public:
bool operator()(const pair<int, int>& a,
const pair<int, int>& b) const
{
return (a.second - a.first) > (b.second - b.first) ||
(((a.second - a.first) == (b.second - b.first)) &&
a.second > b.second);
}
};
int main()
{
int n = 0, x = 0;
cin >> n >> x;
vector<size_t> v(n, 0);
for(int i = 0; i < n; i++)
{
cin >> v[i];
}
// first:区间内值加和,pair存储区间 second:凑数
priority_queue<pair<int, int>,
vector<pair<int, int>>, Greater_pq> pq;
for(int i = 0; i < n; i++)
{
int sum = 0;
for(int j = i; j < n; j++)
{
sum += v[j];
if(sum >= x)
{
pq.push( pair<int, int>(i, j));
break;
}
}
}
cout << pq.top().first +1 << " "
<< pq.top().second +1 << endl;
}
提交截图：
通过了 20% 的测试案例，其他案例由于时间复杂度过高依然没有通过。
时间复杂度分析：
这个方案与
multiset类似，也是使用了两层循环。但是，由于priority_queue的插入操作是 O(log n)，每次插入新的区间时都需要 O(log n) 的时间。因此，总的时间复杂度是
O(n^2 * log n)，这比multiset实现更慢，因为每次插入都增加了额外的 log n 时间。
方案二（优化–滑动窗口）
对于题目中给出的测试案例，我们有如下双指针法（滑动窗口）实现对数组的O(n)时间复杂度遍历即可得到最小区间的下标：
代码示例：
// 利用 同向双指针/滑动窗口 实现（通过率100%）
int main()
{
int N = 10000000;
int n, x;
int retLen = N;
cin >> n >> x;
vector<int> v(n + 1, 0);
for (int i = 1; i < n; i++) // 注意题目的输出示例下标从1开始
{
cin >> v[i];
}
int retLeft = 0, retRight = 0; // 用来记录最终的最小区间左右两端点
int l = 1, r = 1; // 同向双指针
int sum = 0;
while (r < n)
{
// 进窗口
sum += v[r];
while (sum >= x) // 判断出窗口条件
{
if (r - l + 1 < retLen) // 出现满足出窗口条件的更小区间，更新窗口长度
{
retLeft = l;
retRight = r;
retLen = r - l + 1;
}
// 出窗口
sum -= v[l++];
}
r++;
}
cout << retLeft << " " << retRight << endl;
return 0;
}
提交截图：
时间复杂度分析：
使用了双指针技术，其中一个指针表示区间的起点，另一个指针表示区间的终点。
这两个指针从数组的起始位置开始，向右移动直到找到满足条件的区间。当区间的和大于等于 x 时，左指针向右移动以缩小区间。
这种方法确保了每个元素最多被访问两次（一次被右指针访问，一次被左指针访问），因此时间复杂度是 O(2n)，简化后是
O(n)。
总结
对于这道题我们一共尝试了三种不同的方法来解决数据量过大、对时间复杂度要求高的问题，虽然方案1中两种方法分别使用 multimap 和 priority_queue 来辅助存储遍历数组过程中的值，但是时间复杂度是 O(n^2) 和 O(n^2 * log n)，这在数据量大时会导致超时。而这里使用的滑动窗口可以很好的解决重复遍历的浪费，分别使用两个指针控制访问数组的节奏，不走回头路，最大程度的实现了提升算法效率。
