企业官网建设流程全解析

LeetCode 209 最小长度子数组和（Minimum Size Subarray Sum）题解：滑动窗口与三种算法路线详解

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

导读：本篇技术指南以articles/minimum-size-subarray-sum.md为核心，系统讲解 LeetCode 209「长度最小的子数组」的完整解题路线：从暴力枚举到滑动窗口，再到前缀和 + 二分查找，并逐一剖析它们的直觉、算法步骤、复杂度与常见陷阱。文章结合本仓库python/、cpp/、java/、go/、javascript/、kotlin/、swift/、c/等多语言实现源码，帮助读者在掌握该题的同时，吃透「滑动窗口」与「前缀和 + 二分」两类高频面试算法范式，可直接迁移到同类子数组问题中。

问题定义与前置知识

题目要求：给定一个正整数数组nums和一个正整数target，返回和 ≥ target 的连续子数组的最小长度；如果不存在满足条件的子数组，返回0。

例如：

• target = 7, nums = [2,3,1,2,4,3]，最短子数组为[4,3]，长度为2；
• target = 4, nums = [1,4,4]，最短子数组为[4]或[4]，长度为1。

题目成立的一个关键前提是所有元素均为正整数，这保证了「窗口和」具有单调性（向右扩张只增不减、向左收缩只减不增），也使得前缀和数组严格递增——这是下文三种解法能够成立的根本原因。

动手做题前，需要具备三项基础能力（原文档 Prerequisites 部分）：

• 滑动窗口（Sliding Window）：通过左右指针动态调整元素窗口，寻找满足条件的最优子数组；
• 前缀和数组（Prefix Sum）：预先计算累计和，使任意区间[i, j]的和可在 O(1) 时间内求出；
• 二分查找（Binary Search）：在有序数据中以 O(log n) 时间定位目标值或边界。

解法一：暴力枚举（Brute Force）

直觉

最直接的想法是枚举所有可能的子数组。对每个起始下标i，不断向右扩张直到子数组和达到或超过target，记录此时长度。由于所有数都是正数，一旦从i出发的和已满足条件，就没有必要继续扩张——继续扩张只会让子数组更长，不可能更优，因此可以立即break。

算法步骤

1. 将res初始化为无穷大（infinity/INT_MAX/n + 1等哨兵值）；
2. 对每个起始下标i（0到n-1）：
   • 令curSum = 0；
   • 令j从i扩张到n-1，把nums[j]累加进curSum；
   • 一旦curSum >= target，用j - i + 1更新res并break；
3. 若res仍为无穷大，说明无解，返回0；否则返回res。

核心代码

Python 版本（python 仓库中采用滑动窗口实现，暴力版本见原文档）：

class Solution: def minSubArrayLen(self, target: int, nums: List[int]) -> int: n = len(nums) res = float("inf") for i in range(n): curSum = 0 for j in range(i, n): curSum += nums[j] if curSum >= target: res = min(res, j - i + 1) break return 0 if res == float("inf") else res

该算法在 Java、C++、JavaScript、C#、Go、Kotlin、Swift、Rust 中均有同构实现，完整代码请见 articles/minimum-size-subarray-sum.md 中的 tabs 代码块。

复杂度分析

• 时间复杂度：O(n²)——最坏情况下（例如target很大、始终无法提前 break）每个起点都要扫描到数组末尾；
• 空间复杂度：O(1)额外空间（仅使用常数个变量）。

解法二：滑动窗口（Sliding Window，最优解）

直觉

既然所有元素都是正数，就可以用双指针滑动窗口把时间复杂度从 O(n²) 降到 O(n)：右指针r负责把新元素加入窗口、扩大窗口和；一旦窗口和 ≥target，就不断把左指针l向右收缩，尝试去掉左侧元素、缩小窗口，在每次收缩前记录当前窗口长度。因为从左边移除元素只会让总和减小，所以「收缩」与「求最小长度」可以同步进行，窗口始终保持「满足条件的最短前缀形态」。

算法步骤

1. 初始化l = 0、total = 0、res = infinity；
2. 遍历右指针r（0到n-1）：
   • 将nums[r]加入total；
   • 只要total >= target：
     • 用r - l + 1更新res（取最小值）；
     • 从total中减去nums[l]，l右移一位；
3. 若res仍为无穷大，返回0，否则返回res。

注意第 2 步内层是while而非if：窗口可能同时容纳多个可移除元素，必须持续收缩直到和重新小于target。

核心代码（Python）

class Solution: def minSubArrayLen(self, target: int, nums: List[int]) -> int: l, total = 0, 0 res = float("inf") for r in range(len(nums)): total += nums[r] while total >= target: res = min(r - l + 1, res) total -= nums[l] l += 1 return 0 if res == float("inf") else res

仓库源码印证

本仓库多语言目录下提交的正式实现正是该滑动窗口版本，可作为可直接运行的参考：

• python/0209-minimum-size-subarray-sum.py：res = float('inf')，内层while total >= target收缩；
• java/0209-minimum-size-subarray-sum.java：total -= nums[l++]一行完成「减和 + 左移」；
• javascript/0209-minimum-size-subarray-sum.js：用rightWindow - leftWindow + 1记录窗口长度；
• go/0209-minimum-size-subarray-sum.go：以len(nums)+1作为哨兵值，并在注释中标注Time: O(n), Space: O(1)；
• swift/0209-minimum-size-subarray-sum.swift 与 kotlin/0209-minimum-size-subarray-sum.kt：同为右指针扩张 + 左指针收缩的双循环结构；
• c/0209-minimum-size-subarray-sum.c：在cpt >= target时用内层while (cpt-nums[i] >= target)进一步收缩，等价于「先记录、再尽量缩短」的变体。

对比可见，不同语言实现只是在「哨兵值的选取」（float('inf')/Integer.MAX_VALUE/n + 1/Int.max）和「收缩写法」上有差异，核心循环结构完全一致，这也有力印证了滑动窗口解法的通用性。

复杂度分析

• 时间复杂度：O(n)——l和r各自最多移动 n 次，每个元素至多被加入一次、移除一次；
• 空间复杂度：O(1)额外空间。

解法三：前缀和 + 二分查找（Prefix Sum + Binary Search）

直觉

当数组全为正数时，前缀和数组prefixSum是严格递增的。任意子数组[i, j]的和可以写作prefixSum[j+1] - prefixSum[i]，因此问题转化为：对每个起始下标i，在前缀和数组中二分查找最小的结束下标j，使得prefixSum[j+1] - prefixSum[i] >= target。由于前缀和单调，二分查找可以 O(log n) 完成定位，总体复杂度 O(n log n)。

算法步骤

1. 构建前缀和数组：prefixSum[i]表示前i个元素之和（prefixSum[0] = 0，prefixSum[i+1] = prefixSum[i] + nums[i]）；
2. 对每个起始下标i：
   • 在区间[i, n]内二分查找最小的j，使prefixSum[j+1] - prefixSum[i] >= target；
   • 若找到（l != n），用j - i + 1更新res；
3. 返回res % (n + 1)处理无解情况：res初始为n + 1，若从未更新，取模后恰好返回0。

核心代码（Python）

class Solution: def minSubArrayLen(self, target: int, nums: List[int]) -> int: n = len(nums) prefixSum = [0] * (n + 1) for i in range(n): prefixSum[i + 1] = prefixSum[i] + nums[i] res = n + 1 for i in range(n): l, r = i, n while l < r: mid = (l + r) // 2 curSum = prefixSum[mid + 1] - prefixSum[i] if curSum >= target: r = mid else: l = mid + 1 if l != n: res = min(res, l - i + 1) return res % (n + 1)

二分内使用左闭右开式写法：curSum >= target时把右边界收缩到mid（寻找左边界），否则左边界前进到mid + 1，最终l收敛到第一个满足条件的位置。

复杂度分析

• 时间复杂度：O(n log n)——每个起点做一次 O(log n) 二分；
• 空间复杂度：O(n)——需要额外的前缀和数组。

三种解法对比

滑动窗口在时间与空间上全面占优，是本题及面试中的标准答案；前缀和 + 二分解法则展示了「预处理 + 二分」的思想，当题目后续要求频繁区间求和时（例如配合其他数据结构）更具扩展价值。从仓库提交看，python/0209-minimum-size-subarray-sum.py、java/0209-minimum-size-subarray-sum.java 等正式解答均采用滑动窗口，说明它也是社区公认的最优路线。

常见陷阱（Common Pitfalls）

陷阱一：把>=写成==

题目要求的是子数组和大于等于target，而非恰好等于。常见错误是写成if (sum == target)，这会导致「和已经超过 target」的合法子数组被跳过，最终在明明有解的情况下错误地返回0。判断条件务必使用sum >= target。

陷阱二：忘记处理无解情况

当没有任何子数组的和达到target时，必须返回0。若把res初始化为n + 1或无穷大，却在结尾忘记检查res是否被更新过，就会把哨兵值当作答案返回，产生非法结果。暴力法与滑动窗口的收尾写法是return 0 if res == inf else res；前缀和 + 二分法用res % (n + 1)这一技巧优雅地让「从未更新」映射回0。

陷阱三：窗口收缩过度激进

滑动窗口实现中，有的写法在一次迭代内把左指针连续移动多次，却不重新检查窗口和是否仍满足条件。正确做法是：用while循环，只要sum >= target就持续收缩，并在每个合法位置都更新最小长度——每次收缩前窗口都满足条件，因此都要参与res的候选比较。仓库中 python/0209-minimum-size-subarray-sum.py 的while total >= target循环正是这一正确写法的直接体现。

总结

「长度最小的子数组」是滑动窗口技术的入门必刷题，也是面试中区分「只会暴力」与「掌握双指针优化」的经典分水岭。本篇围绕articles/minimum-size-subarray-sum.md完整梳理了三条路线：

1. O(n²) 暴力枚举——建立基线认知；
2. O(n) 滑动窗口——利用全正数的单调性，一次遍历求出最优解，是本仓库各语言正式提交采用的方案（如 python/0209-minimum-size-subarray-sum.py、go/0209-minimum-size-subarray-sum.go）；
3. O(n log n) 前缀和 + 二分——用空间换时间，展示预处理 + 有序二分的通用范式。

同时牢记三个高频坑：判等条件用>=、无解返回0、收缩窗口要用while。掌握本题后，建议继续挑战仓库内同系列滑动窗口/前缀和题目（如 longest-substring-without-duplicates.md、subarray-sum-equals-k.md、minimum-window-with-characters.md），把「单调性 → 双指针」「区间和 → 前缀和」两套思维真正内化。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode