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的最短子数组螺旋矩阵变种从外向内螺旋非方阵的螺旋遍历前缀和扩展二维前缀和结合哈希表解决更复杂的问题开发商购地变种地块不是必须相邻每个地块有不同收益求最大收益而非最多地块在实际开发工作中这些算法思想也有很多应用场景。比如滑动窗口可以用于网络流量控制、日志分析等前缀和算法在图像处理、数据统计分析中很常见矩阵模拟在处理二维数据时非常有用。 
长河君 · 2026/11/6 6:05:09 · 阅读 1.2k 滑动窗口与前缀和：四道经典算法题解析
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的最短子数组螺旋矩阵变种从外向内螺旋非方阵的螺旋遍历前缀和扩展二维前缀和结合哈希表解决更复杂的问题开发商购地变种地块不是必须相邻每个地块有不同收益求最大收益而非最多地块在实际开发工作中这些算法思想也有很多应用场景。比如滑动窗口可以用于网络流量控制、日志分析等前缀和算法在图像处理、数据统计分析中很常见矩阵模拟在处理二维数据时非常有用。