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]长度为2target 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。算法步骤将res初始化为无穷大infinity/INT_MAX/n 1等哨兵值对每个起始下标i0到n-1令curSum 0令j从i扩张到n-1把nums[j]累加进curSum一旦curSum target用j - i 1更新res并break若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向右收缩尝试去掉左侧元素、缩小窗口在每次收缩前记录当前窗口长度。因为从左边移除元素只会让总和减小所以「收缩」与「求最小长度」可以同步进行窗口始终保持「满足条件的最短前缀形态」。算法步骤初始化l 0、total 0、res infinity遍历右指针r0到n-1将nums[r]加入total只要total target用r - l 1更新res取最小值从total中减去nums[l]l右移一位若res仍为无穷大返回0否则返回res。注意第 2 步内层是while而非if窗口可能同时容纳多个可移除元素必须持续收缩直到和重新小于target。核心代码Pythonclass 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.pyres float(inf)内层while total target收缩java/0209-minimum-size-subarray-sum.javatotal - 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[j1] - prefixSum[i]因此问题转化为对每个起始下标i在前缀和数组中二分查找最小的结束下标j使得prefixSum[j1] - prefixSum[i] target。由于前缀和单调二分查找可以 O(log n) 完成定位总体复杂度 O(n log n)。算法步骤构建前缀和数组prefixSum[i]表示前i个元素之和prefixSum[0] 0prefixSum[i1] prefixSum[i] nums[i]对每个起始下标i在区间[i, n]内二分查找最小的j使prefixSum[j1] - prefixSum[i] target若找到l ! n用j - i 1更新res返回res % (n 1)处理无解情况res初始为n 1若从未更新取模后恰好返回0。核心代码Pythonclass 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)——需要额外的前缀和数组。三种解法对比解法核心思想时间复杂度空间复杂度适用场景暴力枚举枚举所有起点并扩张O(n²)O(1)数组规模小、仅作教学理解滑动窗口右扩左缩双指针O(n)O(1)首选一次遍历即可前缀和 二分单调前缀和上二分O(n 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完整梳理了三条路线O(n²) 暴力枚举——建立基线认知O(n) 滑动窗口——利用全正数的单调性一次遍历求出最优解是本仓库各语言正式提交采用的方案如 python/0209-minimum-size-subarray-sum.py、go/0209-minimum-size-subarray-sum.goO(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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/9/18 3:53:39 · 阅读 1.2k LeetCode 209 最小长度子数组和（Minimum Size Subarray Sum）题解：滑动窗口与三种算法路线详解
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]长度为2target 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。算法步骤将res初始化为无穷大infinity/INT_MAX/n 1等哨兵值对每个起始下标i0到n-1令curSum 0令j从i扩张到n-1把nums[j]累加进curSum一旦curSum target用j - i 1更新res并break若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向右收缩尝试去掉左侧元素、缩小窗口在每次收缩前记录当前窗口长度。因为从左边移除元素只会让总和减小所以「收缩」与「求最小长度」可以同步进行窗口始终保持「满足条件的最短前缀形态」。算法步骤初始化l 0、total 0、res infinity遍历右指针r0到n-1将nums[r]加入total只要total target用r - l 1更新res取最小值从total中减去nums[l]l右移一位若res仍为无穷大返回0否则返回res。注意第 2 步内层是while而非if窗口可能同时容纳多个可移除元素必须持续收缩直到和重新小于target。核心代码Pythonclass 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.pyres float(inf)内层while total target收缩java/0209-minimum-size-subarray-sum.javatotal - 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[j1] - prefixSum[i]因此问题转化为对每个起始下标i在前缀和数组中二分查找最小的结束下标j使得prefixSum[j1] - prefixSum[i] target。由于前缀和单调二分查找可以 O(log n) 完成定位总体复杂度 O(n log n)。算法步骤构建前缀和数组prefixSum[i]表示前i个元素之和prefixSum[0] 0prefixSum[i1] prefixSum[i] nums[i]对每个起始下标i在区间[i, n]内二分查找最小的j使prefixSum[j1] - prefixSum[i] target若找到l ! n用j - i 1更新res返回res % (n 1)处理无解情况res初始为n 1若从未更新取模后恰好返回0。核心代码Pythonclass 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)——需要额外的前缀和数组。三种解法对比解法核心思想时间复杂度空间复杂度适用场景暴力枚举枚举所有起点并扩张O(n²)O(1)数组规模小、仅作教学理解滑动窗口右扩左缩双指针O(n)O(1)首选一次遍历即可前缀和 二分单调前缀和上二分O(n 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完整梳理了三条路线O(n²) 暴力枚举——建立基线认知O(n) 滑动窗口——利用全正数的单调性一次遍历求出最优解是本仓库各语言正式提交采用的方案如 python/0209-minimum-size-subarray-sum.py、go/0209-minimum-size-subarray-sum.goO(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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考