一、真题题目描述有一个N个整数的数组和一个长度为M的窗口窗口从数组内的第一个数开始滑动直到窗口不能滑动为止每次窗口滑动产生一个窗口和窗口内所有数的和求窗口滑动产生的所有窗口和的最大值。输入描述第一行输入一个正整数N表示整数个数。0N100000第二行输入N个整数整数的取值范围为[-100,100]。第三行输入一个正整数MM代表窗口的大小M100000且MN。输出描述窗口滑动产生所有窗口和的最大值。示例 1输入输出示例仅供调试后台判题数据一般不包含示例输入612 10 20 30 15 233输出68二、算法核心滑动窗口1. 为什么必须优化暴力法对每个窗口位置重新累加 MM 个数。复杂度 O(N×M) 。后果运算量高达 5×10^9 C 语言虽快但也无法在 1 秒内完成必然超时 (TLE)。滑动窗口法原理相邻窗口只有“一进一出”。公式NewSum OldSum - OutElement InElement。复杂度O(N)。只需遍历一次数组运算量约 10^5 耗时 2ms。2. 算法步骤动态分配内存根据输入的 N 使用malloc申请数组空间避免栈溢出。计算初始和累加前 M 个元素。滑动更新从第 M 个元素开始遍历每次减去滑出的元素加上滑入的元素并更新最大值。释放内存使用free释放堆内存防止泄漏虽然进程结束会自动回收但这是 C 程序员的素养。三、C 语言硬核实现 (C99 标准)本代码特点动态内存使用malloc应对 N 的变化避免固定大数组浪费内存或栈溢出。高效 IO使用scanf和printf这是 C 语言最快的标准输入输出方式。类型安全使用long long存储累加和彻底杜绝整数溢出风险。零依赖纯标准 C 库无需任何额外头文件兼容所有编译器。#include stdio.h #include stdlib.h // for malloc, free int main() { int n; // 1. 读取 N if (scanf(%d, n) ! 1) { return 0; } // 2. 动态分配内存 // 注意在栈上定义 int nums[100000] 可能导致栈溢出尤其在递归或复杂函数中 // 使用 malloc 在堆上分配安全且灵活 int *nums (int *)malloc(n * sizeof(int)); if (nums NULL) { fprintf(stderr, Memory allocation failed!\n); return 1; } // 3. 读取数组元素 for (int i 0; i n; i) { scanf(%d, nums[i]); } int m; // 4. 读取 M if (scanf(%d, m) ! 1) { free(nums); // 异常退出前释放内存 return 0; } // 边界条件检查 if (m 0 || m n) { printf(0\n); free(nums); return 0; } // --- 核心算法滑动窗口 --- // 使用 long long 防止累加溢出 (虽然本题范围 int 够用但这是最佳实践) long long currentSum 0; // 1. 计算第一个窗口的和 (索引 0 到 m-1) for (int i 0; i m; i) { currentSum nums[i]; } long long maxSum currentSum; // 2. 滑动窗口 // i 代表当前新进入窗口的元素索引 // 窗口范围变为 [i-m1, i] // 移出的元素索引为 i-m for (int i m; i n; i) { // 状态转移新和 旧和 新进 - 移出 currentSum nums[i]; currentSum - nums[i - m]; if (currentSum maxSum) { maxSum currentSum; } } // 5. 输出结果 printf(%lld\n, maxSum); // 6. 释放内存 free(nums); nums NULL; // 避免悬空指针 return 0; }✅ C 语言版代码亮点解析动态内存管理 (malloc/free)痛点如果直接写int nums[100000];这是在栈 (Stack)上分配。在某些严格限制栈大小的环境如某些嵌入式或特定判题系统大数组会导致Stack Overflow。解决malloc在堆 (Heap)上分配内存空间更大且灵活。记得最后free体现专业素养。数据类型选择 (long long)虽然题目数值小但在 C 语言中int通常是 32 位。若题目变种导致数值增大累加和极易溢出。使用long long(至少 64 位) 并配合%lld格式化输出是算法题的标准防御姿态。极致的 IO 效率scanf和printf是 C 语言的标准 IO经过高度优化读取 10 万整数仅需几毫秒远快于 C 未加速的cin与加速后的cin持平。指针操作通过nums[i]访问数组底层是指针运算*(nums i)这是 C 语言最高效的随机访问方式。四、逻辑推演与内存视图输入6 12 10 20 30 15 23 3内存布局 (简化)地址: [0] [1] [2] [3] [4] [5] 数值: 12 10 20 30 15 23 ^ ^ | | 移出(i-3) 移入(i)执行流程初始currentSum 121020 42。maxSum 42。i3currentSum 42 30 (nums[3]) - 12 (nums[0]) 60。maxSum 60。i4currentSum 60 15 (nums[4]) - 10 (nums[1]) 65。maxSum 65。i5currentSum 65 23 (nums[5]) - 20 (nums[2]) 68。maxSum 68。结束打印 68释放内存。五、C 语言特有避坑指南⚠️栈溢出 (Stack Overflow)错误写法int nums[100000];放在main函数内。风险默认栈大小通常仅 1MB~8MB大数组可能撑爆栈。正确写法使用malloc或在main外定义为全局变量。本文采用了更规范的malloc。格式化占位符int对应%d。long long对应%lld。切记如果用%d输出long long在 64 位系统上会得到错误结果。内存泄漏 (Memory Leak)虽然操作系统会在程序结束时回收内存但在函数内部malloc后必须free。这是 C 程序员的基本功也是面试加分项。空指针检查malloc可能失败虽然现代系统很少见务必检查if (nums NULL)。变量初始化C 语言的局部变量不会自动初始化为 0currentSum和maxSum必须显式赋值否则它们是内存中的垃圾值。六、结语C 语言是理解计算机底层运作的钥匙。通过这道题我们不仅掌握了滑动窗口这一通用算法还复习了动态内存分配、指针运算以及IO 优化等 C 语言核心技能。核心口诀“堆上分配防溢出长整累加防越界一进一出滑窗口用完记得 Free 掉”。进阶建议尝试将本题改为“流式处理”即不存储整个数组只维护一个大小为 MM 的循环队列将空间复杂度进一步优化至 O(M) 。掌握 C 语言的这些细节你将能在任何严苛的算法环境中游刃有余。觉得有帮助请点赞、收藏⭐、关注下一期我们将挑战C 语言数据结构手写链表实现 LRU 缓存