笔试题3 -- dd爱框框（滑动窗口内值加和大于x的最小区间）

本文主要是介绍笔试题3 -- dd爱框框（滑动窗口内值加和大于x的最小区间），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

爱框框（滑动窗口内值加和大于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)，这在数据量大时会导致超时。而这里使用的滑动窗口可以很好的解决重复遍历的浪费，分别使用两个指针控制访问数组的节奏，不走回头路，最大程度的实现了提升算法效率。

这篇关于笔试题3 -- dd爱框框（滑动窗口内值加和大于x的最小区间）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---