首页/新闻资讯/正文详情

【C++算法打怪专栏】连续子数组最小和问题:滑动窗口与暴力枚举分析

发布时间:2026/9/26 4:17:41 来源:云帆数科 栏目:资讯中心
【C++算法打怪专栏】连续子数组最小和问题:滑动窗口与暴力枚举分析
【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。

相关推荐

资源组织与依赖分析:构建工具如何读懂你的代码
资源组织与依赖分析:构建工具如何读懂你的代码

1. 先搞清楚资源组织到底在解决什么问题很多人第一次听到“资源组织”这个词,第一反应是“这说的不就是文件夹怎么摆、文件怎么命名吗?”。能这么想不奇怪,因为从表面上看,资源组织确实就是在管理文件。但如果你真的只把它当成“目… · 2026/9/26 4:17:41

OpenAI工程师30天API调用耗资130万美元 测试AI辅助开发极限能力
OpenAI工程师30天API调用耗资130万美元 测试AI辅助开发极限能力

现在, AI来帮忙写代码, 这已经成了科技这个行业里用来提高干活速度的最关键的办法了, 那些大公司都在不停地投钱、花精力去试试看这个本事到底有多大。到了2026年5月16日的那一天, 有个叫彼得施泰因贝格尔的人, 他既是这家公司的员工, 也是这个项目的创办人, 他向外头公开晒出了… · 2026/9/26 4:17:29

Spring Boot 官宣:正式弃用 Java 8,一文讲透升级迁移全流程
Spring Boot 官宣:正式弃用 Java 8,一文讲透升级迁移全流程

1. 引言Java 8 从 2014 年发布至今,曾经陪伴了无数后端开发者走过十年的黄金时代。然而,随着 Spring Boot 3.0 的正式发布,Spring 官方已经明确宣告:Java 8 不再是受支持的基线版本。对于仍然运行在 Java 8 之上的大量存量系统来说… · 2026/9/26 4:17:29

Linux用户与权限管理:从基础概念到实战排查
Linux用户与权限管理:从基础概念到实战排查

如果你刚接触Linux,大概率会在一台服务器前面纠结过这种事:明明数据就在 /home 下,用别人的账号却进不去,用 root 却畅通无阻;新建了一个用户,结果登录之后连命令都敲不了几条。这些现象背后,全… · 2026/9/26 5:05:07

如何注册文件预览器:DSH-better-sidebar的FileViewer API完整参考(匹配算法/取数策略/真实案例)
如何注册文件预览器:DSH-better-sidebar的FileViewer API完整参考(匹配算法/取数策略/真实案例)

如何注册文件预览器:DSH-better-sidebar的FileViewer API完整参考(匹配算法/取数策略/真实案例) 【免费下载链接】DSH-better-sidebar 开放的侧边栏底座,支持三方拓展注册新侧边栏页面。内置文件渲染编辑/终端/侧边对话/Git/子代理… · 2026/9/26 5:05:01

SpringBoot+Vue+MySQL语言考试报名系统毕业设计全攻略
SpringBoot+Vue+MySQL语言考试报名系统毕业设计全攻略

很多同学拿到“语言考试报名系统”这个毕业设计题目时,第一反应是“不就是增删改查吗”,但真做起来会发现,里面藏着一整套围绕“报名状态”的业务逻辑:考生注册、考试计划发布、资格校验、名额限制、审核流转、准考证生成、成绩查… · 2026/9/26 5:05:01

【67GHz射频开关大比拼】
【67GHz射频开关大比拼】

67GHz射频开关大比拼 本文根据Keysight, 思仪,Radiall公开的产品手册,对Keysight U7106F, 思仪80103L和Radiall的R574J02605进行了对比。分别是隔离度VS频率、插损VS频率、和驻波VS频率。 数据来源: 1) Keysight U7106F&#xff0… · 2026/9/26 5:05:01

Docker核心概念拆解:镜像分层、网络排障与数据持久化实战
Docker核心概念拆解:镜像分层、网络排障与数据持久化实战

Docker 核心概念这东西,我一开始是吃了亏才愿意回炉重造的。当时接手一个项目,要把跑着的 MySQL 容器整个搬到新机器,图省事直接docker commit打了个“备份镜像”,结果拖过去启动之后账户全乱、数据时好时坏,最后花了整… · 2026/9/26 5:05:01

卡巴斯基免费版无需激活码:核心功能与安装配置指南
卡巴斯基免费版无需激活码:核心功能与安装配置指南

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 5:04:55

数据库课后习题答案别硬背:当测试用例集刷,效率翻倍
数据库课后习题答案别硬背:当测试用例集刷,效率翻倍

简介:万常选版《数据库原理与设计》课后习题答案资源,覆盖第2至6章及第9章,适合正在学习关系模型、数据库建模、关系数据理论与模式求精的本科生、自学者作为复习与自测材料。压缩包共7个文件,含3个doc参考答案、2个sql示例脚本、… · 2026/9/26 0:00:21

OpenClaw 替代品?Hermes Agent 踩坑实录:macOS 飞书接入 TaoToken 配置
OpenClaw 替代品?Hermes Agent 踩坑实录:macOS 飞书接入 TaoToken 配置

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 0:00:40

向下兼容与向上兼容:接口设计中的兼容性策略与工程实践
向下兼容与向上兼容:接口设计中的兼容性策略与工程实践

一次版本升级事故,是很多团队绕不过去的坎。线上环境里,服务端明明已经上线了新版接口,老的移动端还在照着旧文档传参数。请求一到网关,校验直接拒绝,用户操作失败,客服群炸了锅,开发群里开始互… · 2026/9/26 0:00:46

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码