滑动窗口与前缀和：四道经典算法题解析-云帆数科

1. 算法刷题实战四道经典题目深度解析今天要和大家分享四道非常有意思的算法题目涵盖了滑动窗口、矩阵模拟、前缀和以及贪心算法等多个经典算法知识点。这些题目都来自知名OJ平台在实际面试中也经常被考察。我会从题目分析、解题思路到具体实现一步步带大家攻克这些难题。2. 209. 长度最小的子数组2.1 题目理解与暴力解法这道题要求我们找到一个连续子数组其和≥target并且长度最小。最直观的解法当然是暴力枚举所有可能的子数组def minSubArrayLen(target, nums): min_len float(inf) n len(nums) for i in range(n): current_sum 0 for j in range(i, n): current_sum nums[j] if current_sum target: min_len min(min_len, j - i 1) break return min_len if min_len ! float(inf) else 0这种解法时间复杂度是O(n²)在数据量较大时性能会很差。我们需要更高效的算法。2.2 滑动窗口优化滑动窗口是解决这类子数组问题的利器。基本思路是维护一个窗口通过调整窗口的左右边界来寻找最优解def minSubArrayLen(target, nums): n len(nums) min_len float(inf) left 0 current_sum 0 for right in range(n): current_sum nums[right] while current_sum target: min_len min(min_len, right - left 1) current_sum - nums[left] left 1 return min_len if min_len ! float(inf) else 0这个算法的时间复杂度降到了O(n)因为每个元素最多被访问两次加入窗口和移出窗口。注意滑动窗口的关键在于确定何时移动左指针。这里当sum≥target时我们尝试缩小窗口以寻找更小的满足条件的子数组。3. 59. 螺旋矩阵 II3.1 问题分析与模拟思路这道题要求生成一个n×n的螺旋矩阵数字从1到n²按顺时针方向螺旋填入。解决这类矩阵模拟题的关键是确定遍历的边界和方向。我们可以定义四个边界top、bottom、left、right然后按照右→下→左→上的顺序填充数字每完成一个方向就调整对应的边界。3.2 具体实现代码def generateMatrix(n): matrix [[0]*n for _ in range(n)] num 1 top, bottom 0, n-1 left, right 0, n-1 while num n*n: # 从左到右 for i in range(left, right1): matrix[top][i] num num 1 top 1 # 从上到下 for i in range(top, bottom1): matrix[i][right] num num 1 right - 1 # 从右到左 for i in range(right, left-1, -1): matrix[bottom][i] num num 1 bottom - 1 # 从下到上 for i in range(bottom, top-1, -1): matrix[i][left] num num 1 left 1 return matrix这个算法的时间复杂度是O(n²)因为我们需要填充n²个元素空间复杂度也是O(n²)用于存储矩阵。提示在处理边界条件时要特别注意特别是在矩阵的最后一圈可能只剩一行或一列时要避免重复填充。4. 区间和问题4.1 前缀和算法原理区间和问题通常要求我们快速计算数组中某个区间的元素和。如果直接每次计算时间复杂度是O(n)当查询次数很多时效率不高。前缀和算法可以预处理数组使得每次查询的时间复杂度降为O(1)。基本思想是预先计算从第一个元素到当前元素的和def prefixSum(nums): n len(nums) prefix [0]*(n1) for i in range(n): prefix[i1] prefix[i] nums[i] return prefix # 查询区间[i,j]的和 def query(prefix, i, j): return prefix[j1] - prefix[i]4.2 实际应用示例假设我们有一个数组[1,3,5,7,9]预处理后的前缀和数组为[0,1,4,9,16,25]。要查询区间[1,3]的和sum prefix[4] - prefix[1] 16 - 1 15确实35715验证了算法的正确性。5. 开发商购买土地问题5.1 问题描述与贪心策略这个问题描述开发商需要购买一系列相邻的土地块每个地块有不同的价格要求在预算范围内购买尽可能多的地块。这实际上是一个典型的滑动窗口问题可以用类似于长度最小的子数组的思路来解决但目标是最大化窗口大小而非最小化。5.2 具体解法实现def maxLand(prices, budget): max_count 0 current_sum 0 left 0 for right in range(len(prices)): current_sum prices[right] while current_sum budget: current_sum - prices[left] left 1 max_count max(max_count, right - left 1) return max_count这个算法的时间复杂度是O(n)空间复杂度是O(1)非常高效。经验分享在实际编码比赛中滑动窗口类问题的关键在于确定窗口何时扩展、何时收缩。这类问题通常都有固定的模板可以套用。6. 算法总结与比较让我们总结一下这四道题目用到的算法技巧题目使用算法时间复杂度空间复杂度长度最小的子数组滑动窗口O(n)O(1)螺旋矩阵 II模拟O(n²)O(n²)区间和前缀和预处理O(n)查询O(1)O(n)开发商购地滑动窗口O(n)O(1)在实际面试中面试官可能会要求你不仅写出代码还要分析时间/空间复杂度甚至提出优化方案。因此理解每种算法的适用场景和性能特点非常重要。7. 常见错误与调试技巧在实现这些算法时新手常犯的一些错误包括滑动窗口问题忘记在移动左指针时从current_sum中减去对应的值边界条件处理不当特别是当所有元素和仍小于target时螺旋矩阵问题边界更新时机不对导致重复填充或漏填对于奇数n的中心点处理不当前缀和问题前缀和数组大小设置错误应该是n1查询时索引计算错误调试技巧对于滑动窗口问题可以在循环中加入打印语句输出当前窗口的左右边界和sum值对于矩阵问题可以打印中间结果矩阵观察填充过程使用小规模测试用例手动验证算法正确性8. 进阶思考与扩展掌握了这些基础算法后可以尝试解决一些变种问题长度最小的子数组变种允许包含负数的情况寻找和恰好等于target的最短子数组螺旋矩阵变种从外向内螺旋非方阵的螺旋遍历前缀和扩展二维前缀和结合哈希表解决更复杂的问题开发商购地变种地块不是必须相邻每个地块有不同收益求最大收益而非最多地块在实际开发工作中这些算法思想也有很多应用场景。比如滑动窗口可以用于网络流量控制、日志分析等前缀和算法在图像处理、数据统计分析中很常见矩阵模拟在处理二维数据时非常有用。

企业数字化 ERP 产品动态

相关推荐

Checklist设计编写规范及模板：条目规则、试跑与落地治理

清单这东西，几乎人人都写过，但真正写到“能被人照着执行、执行完真能挡住问题”的，比例低得吓人。我见过太多这样的文件：二十页的文档，通篇写着“注意”“确保”“严格检查”，执行的人扫一眼、签个字、归档… · 2026/11/6 6:04:08

算法竞赛紫题训练：突破1900-2100分的关键方法

1. 项目背景与核心价值"20260312紫题训练"这个看似神秘的标题，实际上揭示了算法竞赛选手的一种高效训练方法。作为经历过ACM-ICPC、Codeforces等赛事的老兵，我深知紫题（Purple Problem）在算法竞赛训练体系中的特殊地位—… · 2026/11/6 6:04:08

DPDK mbuf结构体拆解：长度字段、零拷贝与收发包避坑

收包回调里的那段代码，卡了我整整一个下午：明明抓包工具里看到的报文长度是 1514，我自己拼出来的pkt_len却是 1024，后面数据全被截断，转发出去对端直接丢包。最后翻到struct rte_mbuf的定义里才发现，我把da… · 2026/11/6 6:04:08

Windows 11安装MySQL 8.0完整指南与常见问题解决

1. MySQL 8.0在Windows 11上的完整安装指南作为数据库管理员，我经常需要在各种Windows系统上部署MySQL。最近在Windows 11上安装MySQL 8.0时，发现官方安装包虽然简单，但隐藏了不少坑点。本文将分享我从下载到配置的完整过程，包含… · 2026/11/6 13:48:01

KaiwuDB分布式数据库安装部署与性能调优实战

1. 初识KaiwuDB：一款值得关注的新型数据库第一次听说KaiwuDB是在一个技术社区的热门讨论帖里，当时几位资深DBA正在比较各种新型数据库的性能特点。作为一个长期使用传统关系型数据库的开发者，我对这类新兴产品总是保持着谨慎但开放的态度。经… · 2026/11/6 13:48:01

E3-1231 v3+B85-D3H黑苹果OpenCore EFI配置与避坑

简介：面向 Intel E3 1231V3 处理器搭配 B85 D3H 主板的黑苹果 EFI 引导配置包，主要服务于希望在非苹果硬件上安装并运行 macOS 的进阶玩家与装机爱好者。内容围绕 Clover/OpenCore 类引导所需组件展开，包含 ACPI 补丁、驱动内核扩展、设备属性… · 2026/11/6 13:40:21

CentOS 7下Docker Redis三主三从集群一键部署脚本与避坑

简介：针对 CentOS 7.x 环境下希望快速搭建容器化 Redis 集群的 Linux 运维人员与后端开发者，提供一套可传递参数后自动执行的 shell 部署方案，用于减少逐节点配置、容器编排和基础环境准备中的重复操作，适合实验环境验证及中小项目… · 2026/11/6 13:37:02

工业控制系统深度解析：35 电机速度控制

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