[略——开始正文]先说我为什么要把“算法题-27”单独拎出来复盘。它不是一道特别难的题但回顾它的过程比当初 AC 的瞬间更有价值一道连续子数组求和的问题串起了暴力枚举、前缀和加二分查找、滑动窗口三条优化路径。这篇文章会给你完整可跑的代码、提交时我真实踩过的坑以及面试时怎么把“为什么这样优化”讲清楚。适合刷题新手、准备算法面试的人也适合想系统理解经典题型的人。1. 这道题到底在考什么读题比动手更值钱我把题目原样贴在这里给定一个只包含正整数的数组nums和一个正整数target返回满足“子数组和 ≥ target”的最短连续子数组长度如果不存在返回 0。这类题有个特点题干特别短限制条件只有“正整数”三个字但恰恰是这三个字决定了解法的走向。我见过不少人在这一步栽跟头忽略掉它直接套前缀和和二分然后被负数数据搞挂。1.1 拿到题先做三件事第一件事确认数据规模。如果n ≤ 2000双层循环暴力枚举可以直接过如果n 10^5就必须想O(n log n)甚至O(n)的做法。几乎所有算法题的第一道坎都是数据规模不是思路本身。第二件事确认输出语义。这题要求“不存在返回 0”不是返回 -1也不返回数组长度。空数组也返回 0。这种细节在面试时特别容易被追问。第三件事确认“正整数”这个条件不是摆设。它保证了前缀和数组严格递增也保证了后面滑动窗口一定能用。如果把数组换成有负数的情况同样的解题思路会瞬间失效。1.2 为什么这类题高频连续子数组问题在面试里出现频率极高变体也很多求和等于某个值的子数组数量、和不超过 target 的最长长度、和大于等于 target 的最短长度、乘积最大或最小的子数组……剥开外壳内核都是同一件事维护一段连续区间并快速判断这段区间是否满足条件。把这一题吃透等于把一整个题型都串起来了。这也是我不建议只背题解的原因曡题不如曡“模式”。2. 先写暴力解法用 O(n²) 换来“完全确定正确性”2.1 暴力代码与第一次复杂度判断先写最直觉的版本枚举左端点i然后从i开始向右扩展右端点j边扩展边累加一旦累加和达到target就记录长度并跳出内层循环。int minSubArrayLen(int target, vectorint nums) { int n nums.size(); int ans n 1; for (int i 0; i n; i) { int sum 0; for (int j i; j n; j) { sum nums[j]; if (sum target) { ans min(ans, j - i 1); break; } } } return ans n 1 ? 0 : ans; }这里有一个细节因为数组全是正整数sum随着j变大只会越来越大所以一旦满足sum target当前i就不用继续往后扫了。这个break能剪掉不少内层循环但最坏情况下比如整个数组加起来都不到target每个i都会一路扫到数组末尾所以时间复杂度依然是O(n²)。有人会问为什么不用三重循环枚举所有区间因为三重循环会反复做大量无意义的求和运算。我们只需要在扩展右端点时把sum累加进去就能一次性覆盖所有以i开头的区间根本不需要第三层循环重新求和。这是暴力解法里最值得记住的一个小优化思路。2.2 复杂度计算什么时候用 O什么时候用 Θ聊复杂度之前先厘清一个概念O表示上界Θ表示紧密界。面试里我们习惯说“这个算法是 O(n²)”严格来讲这句话只说了“它不会比 n² 慢太多”并没有说明它到底是不是一定在 n² 这个量级。拿暴力代码举例内层循环因为有break并不是每个i都会跑满n - i次。最好情况下第一个元素就满足条件很快结束最坏情况下整个数组和小于target每个i都扫到末尾。所以严格说这段代码是O(n²)上界下限是Ω(n)两者不相等因此不能直接说它是Θ(n²)。而滑动窗口版本因为每个元素最多被left和right各访问一次所以既有O(n)上界又有Ω(n)下界才能放心地说是Θ(n)。这个区分在面试里是加分项。面试官问到“这个算法复杂度是多少”时能主动说出“最坏 O(n²)但因为有 break 实际平均会好一些”比干巴巴一句“O(n²)”可信得多。重要的是用数据说服自己必须优化n 10^5时O(n²)是10^10次累加按每秒10^8次运算估算需要 100 秒这在竞赛或面试现场都完全不可接受。3. 前缀和 二分先学会把“区间和”变成“两个端点的差”3.1 关键推导暴力解法慢在每次都要重新累加一段区间。如果能提前算好前缀和那就把“区间和”转换成了“两个端点的差”定义prefix[i]表示nums[0..i-1]的和那么子数组nums[i..j-1]的和就是prefix[j] - prefix[i]。题目要求区间和 ≥ target也就是prefix[j] - prefix[i] target移项后变成prefix[j] prefix[i] target。由于数组全是正整数prefix严格递增我们可以用二分查找快速找到第一个满足prefix[j] prefix[i] target的j。这就是前缀和二分的优化逻辑。3.2 代码实现与边界注意int minSubArrayLen(int target, vectorint nums) { int n nums.size(); vectorlong long prefix(n 1, 0); for (int i 0; i n; i) { prefix[i 1] prefix[i] nums[i]; } int ans n 1; for (int i 0; i n; i) { long long need prefix[i] target; auto it lower_bound(prefix.begin() i 1, prefix.end(), need); if (it ! prefix.end()) { int j it - prefix.begin(); ans min(ans, j - i); } } return ans n 1 ? 0 : ans; }这里有两个容易出问题的细节。第一prefix的长度是n 1prefix[0] 0必须保留它表示空区间的前缀和。如果不保留从下标 0 开始的子数组就找不到了。第二内层循环里lower_bound的起点必须从i 1开始保证子数组非空否则可能找到一个长度为 0 的“空区间”当作答案。3.3 大多数人会忽略的整数溢出我最初用int存prefix本地小样本测试一切正常提交后一个大用例直接失败。原因是n 10^5每个元素值达到10^9prefix[n]超过int上限。这种问题不是逻辑错误而是类型选择错误特别隐蔽往往只在极限数据下触发。建议涉及累加和、乘积这类数值的题目一律优先考虑long long。这不是过度设计是提前排雷。很多在线判题系统给出的边界数据就是专门敲打这种粗心大意的。4. 滑动窗口 O(n)把左右指针当成动态区间4.1 双指针为什么能到 O(n)前缀和二分已经是O(n log n)但对这道题来说还不是终点。仔细观察会发现两个指针left和right在整个过程中只会各自向右移动每个元素最多被left访问一次、被right访问一次所以整体是严格的O(n)。核心思路就两句话右指针负责扩展窗口让窗口和变大一旦窗口和满足条件左指针负责收缩窗口尝试让窗口变短。每次满足条件时记录一下当前窗口长度最后就能得到最短长度。4.2 滑动窗口代码int minSubArrayLen(int target, vectorint nums) { int n nums.size(); int left 0, ans n 1; long long sum 0; for (int right 0; right n; right) { sum nums[right]; while (sum target) { ans min(ans, right - left 1); sum - nums[left]; left; } } return ans n 1 ? 0 : ans; }如果你更习惯 Python逻辑完全一致def min_sub_array_len(target, nums): n len(nums) left 0 ans n 1 total 0 for right in range(n): total nums[right] while total target: ans min(ans, right - left 1) total - nums[left] left 1 return 0 if ans n 1 else ans注意ans的初始值我设成了n 1。这是一个常见的技巧因为最短长度不可能超过n所以用一个“比所有可能答案都大”的初始值最后判断ans是否仍是n 1就能知道到底有没有找到合法区间。如果初始值设成0或者INT_MAX要么没法做“是否存在”的判断要么多一层比较逻辑容易混乱。4.3 为什么这个题必须是正整数滑动窗口能工作的前提是窗口在“收缩”时不会出现异常当左指针向右移动窗口区间变短即使移出一个负数导致窗口和变大窗口的逻辑就崩了因为“更短的区间”可能反而满足条件双指针就没法保证当前窗口是候选最短区间。一旦数组包含负数正确的做法一般是前缀和配合哈希表或平衡树去查找满足条件的prefix[j] - prefix[i]思路会复杂一个档次。因此题目限定“正整数”不是在为难你而是在给你发一个“滑动窗口可用”的信号。面试时主动说出这一点说明你真的理解了这个算法而不是背下来的模板。4.4 三种解法对比解法时间复杂度空间复杂度适用条件暴力枚举O(n²)O(1)数据规模很小适合验证正确性前缀和二分O(n log n)O(n)数组元素非负前缀和单调递增滑动窗口O(n)O(1)数组元素非负且需要找最短/最长连续子数组从表格可以清楚看到滑动窗口在时间、空间上都占优但它的适用条件是三者中最苛刻的。实际面试中先分析条件、再选算法永远比上来就写最优解安全。5. 提交后的踩坑复盘不是一次就能 AC5.1 我的完整排查链路这道题我并没有一次通过。复盘时的顺序大概是这样的你可以直接参考这条思路来排查自己的代码。第一次暴力版本地测试通过。用小的随机数组和后手验证几个用例一切正常但提交直接超时。这一步说明逻辑没错瓶颈在复杂度。第二次我尝试在内层循环加判断条件提前退出比如当sum 剩余元素和 target时直接跳过。这种剪枝对大数据有一定效果但最坏情况依然超时。说明这类优化只是“治标”并没有改变复杂度级别。第三次改用前缀和二分后小数据过了大数据挂掉。我一开始以为是二分边界写错后来把前缀和数组打印出来才发现prefix[n]已经溢出了int。把prefix改成long long后这个版本的用例全部通过。第四次滑动窗口版本逻辑改好后又踩了一个“无解返回值”的坑。空数组时ans保持n 1 1我不小心直接返回了1正确结果应该返回0。这个 bug 让我意识到任何边界条件下都要想清楚“不存在”和“存在但长度为 1”两种情况。5.2 调试时打印什么如果滑动窗口出了问题我建议先打印right、left、sum和ans四个关键变量。比如在while循环收缩窗口前加一行输出printf(right%d left%d sum%lld new_len%d\n, right, left, sum, right - left 1);你会看到窗口状态的变化过程right一直在递增left在满足条件后追赶rightans不断被更小的值覆盖。如果某个用例下left突然超过了right说明while的收缩条件写错了或者数组里有不符合预期的负数值。5.3 边界用例清单我自己整理了一份针对这道题的边界用例表每次写完代码都用它验证一遍输入target期望输出说明[]50空数组直接返回 0[10]51单个元素就满足条件[1, 2, 3]1000所有元素和不够不存在合法区间[1, 2, 3]63整个数组刚好满足[2, 3, 1, 2, 4, 3]72标准示例答案是[4,3][1, 1, 1, 1]11第一个元素就满足最短长度是 1这些用例覆盖了空输入、单元素、无解、刚好满足、标准示例几种情况能拦住大部分低级错误。6. 一道题铺开一张网算法工程师该掌握的知识脉络6.1 从这道题往外扩展的算法地图刷题最忌讳孤立地做题。把“算法题-27”放在整个算法体系里看它至少能牵引出这些方向方向代表算法典型应用场景排序归并排序、堆排序、快速排序TOP K、前 K 大、逆序对字符串KMP、字典树模式匹配、前缀统计图论Tarjan、匈牙利算法强连通分量、二分图匹配搜索DFS、BFS、剪枝、A*暴力枚举的进阶形态动态规划背包问题、区间 DP贪心无法保证的场景机器学习聚类、随机森林、深度学习特征工程、模型训练你会发现很多看起来毫无关联的算法底层思维是相通的。比如 KMP 强调的是“已经匹配过的信息不要重复计算”滑动窗口强调的是“已经计算过的区间信息不要重复扫描”前缀和强调的是“区间信息提前预处理”本质上都是同一个思路用空间换时间消除重复计算。日常工程里也是如此。嵌入式领域常见滑动平均滤波、PID 控制机器学习领域常见聚类和随机森林这些都不是算法题里凭空冒出来的概念而是同一套复杂度分析思想在不同领域的落地。6.2 面试官视角代码能 AC 只是起点我面试过不少候选人最怕的不是算法题不会做而是上来就背模板式写代码。代码 AC 只能证明他记住了这道题不能证明他理解这个算法。作为面试者正确的表现方式是先确认数据规模和边界条件然后说“我先给一个暴力解法验证正确性”再逐步分析瓶颈在哪里最后落到最优解。哪怕最终解法不是最优你完整展示了思考链路面试官反而更认可。如果你要准备算法面试我建议你练完一道题后多问自己三个问题这个解法为什么在这个数据规模下可行它的局限性是什么如果去掉题目的某个限制条件解法会怎么变化这三个问题很多候选人答不上来但恰恰是面试官最爱问的。我在“算法题-27”上最大的收获不是代码通过了一个 case而是终于把“为什么滑动窗口必须配正整数数组”这种以前半懂不懂的问题彻底想明白了。如果你也困在某个瓶颈期建议把你最近做的每道题都用同样的方式复盘一遍暴力解法写出来、优化路径讲出来、边界用例列出来。不用贪多一周彻底吃透两三道比囫囵吞五十道有效得多。