【C算法打怪专栏】连续子数组最小和问题滑动窗口与暴力枚举分析在刷题过程中求“连续m mm个元素的区间和”是一个极其经典的问题。本文将以洛谷 P1614 爱与愁的心痛 为例讲解暴力枚举与滑动窗口 (O ( n ) O(n)O(n)) 两种解法。一、题目描述给定n nn个整数和一个整数m mm求连续m mm个数的和的最小值。输入第一行为n , m n, mn,m接下来的n nn行每行一个整数a i a_iai​。输出连续m mm个数的和的最小值。数据范围0 ≤ m ≤ n ≤ 3000 0 \le m \le n \le 30000≤m≤n≤30001 ≤ a i ≤ 100 1 \le a_i \le 1001≤ai​≤100。二、方法一双重循环暴力枚举最直观的做法是枚举所有可能的起始位置i ii然后计算从i ii开始的连续m mm个数的和最后维护一个最小值。C 代码实现#includebits/stdc.husingnamespacestd;intmain(){// 提高 IO 效率ios::sync_with_stdio(false);cin.tie(nullptr);intn,m;if(!(cinnm))return0;vectorinta(n);for(inti0;in;i){cina[i];}// 特殊情况判断if(m0){cout0\n;return0;}intmin_aINT_MAX;// 外层循环枚举起点注意边界为 n - mfor(inti0;in-m;i){longlongans0;for(intji;jim;j){ansa[j];}if(ansmin_a){min_aans;}}coutmin_a\n;return0;}复杂度分析时间复杂度O ( n × m ) O(n \times m)O(n×m)。在n , m ≤ 3000 n, m \le 3000n,m≤3000时计算量约9 × 10 6 9 \times 10^69×106可以在1.0 s 1.0\text{s}1.0s内轻松通过。空间复杂度O ( n ) O(n)O(n)用于存储原数组。三、方法二滑动窗口最优解当数据规模扩大到n , m ≤ 10 5 n, m \le 10^5n,m≤105时暴力做法会超时TLE。此时可以使用滑动窗口思想先计算前m mm个元素的和current_sum。窗口向右移动一步时加上新移入的元素减去移出的元素即可在O ( 1 ) O(1)O(1)时间内得到新窗口的和。C 代码实现#includeiostream#includevector#includeclimits#includealgorithmusingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn,m;if(!(cinnm))return0;vectorinta(n);for(inti0;in;i){cina[i];}if(m0){cout0\n;return0;}// 1. 初始化第一个窗口的和intcurrent_sum0;for(inti0;im;i){current_suma[i];}intmin_acurrent_sum;// 2. 滑动窗口更新最小值for(intim;in;i){current_suma[i]-a[i-m];// 滑入 a[i]滑出 a[i-m]min_amin(min_a,current_sum);}coutmin_a\n;return0;}复杂度分析时间复杂度O ( n ) O(n)O(n)整个数组只需遍历一次。空间复杂度O ( n ) O(n)O(n)。四、坑点与总结边界条件控制外层循环终止条件是i n - m写成i n会导致内层循环越界访问造成RE。特殊输入当m 0 m 0m0时连续0 00个数的和为0 00需要提前退出。初始化维护最小值的变量应初始化为足够大的数如INT_MAX。