2026/9/10 2:51:05
FEATURED · 精选文章  拓展)
LeetCode 209. Minimum Size Subarray SumGo 滑动窗口解法与 O(n log n) 拓展【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读LeetCode 209 是一道经典的滑动窗口Sliding Window入门题给定一个由正整数组成的数组和目标值 s需要找出和 ≥ s 的最短连续子数组。本篇文章以 LeetCode-Go 仓库中 0209.Minimum-Size-Subarray-Sum 的题解文档为核心结合仓库内完整的 Go 实现与单元测试逐行拆解双指针滑动窗口的原理、边界处理与复杂度分析并进一步推导题目要求的 O(n log n) 进阶解法前缀和 二分查找帮助你彻底掌握这一类最短/最长连续子数组满足某条件问题的通用套路。题目理解原题描述给定一个由 n 个正整数组成的数组nums和一个正整数s找出和 ≥s的最短连续子数组contiguous subarray的长度。如果不存在这样的子数组返回 0。示例 1输入: s 7, nums [2,3,1,2,4,3] 输出: 2 解释: 子数组 [4,3] 是满足和 ≥ 7 的最短连续子数组Follow up进阶要求如果你已经想出了 O(n) 的解法请尝试再实现一个时间复杂度为 O(n log n) 的解法。从题目描述可以提炼出三个关键约束数组元素全为正整数这是滑动窗口解法能够成立的前提正整数保证右指针扩张时窗口和单调不减左指针收缩时窗口和单调不增要求的是连续子数组因此不能排序必须保留元素原有的相对顺序求的是满足条件的最小长度一旦不存在解要返回 0 而不是某个默认值。题目大意给定一个整型数组和一个数字s找到数组中最短的一个连续子数组使得连续子数组的数字之和sum s返回最短连续子数组的长度。若整个数组之和都小于s则返回 0。解题思路滑动窗口双指针本题的官方推荐解法是滑动窗口。在窗口[i, j]之间不断往后移动如果当前窗口内总和小于s就扩大右边界j不断加入右边的值直到sum s此时记录窗口长度并尝试收缩左边界i不断缩小直到sum s此时右边界又可以继续往右移动重复上述过程。整个过程右指针只向右走一遍左指针也只向右走一遍因此整体时间复杂度为 O(n)。为了便于理解我们用示例s 7, nums [2,3,1,2,4,3]手工模拟一遍窗口的伸缩过程步骤窗口内容窗口和sum ≥ 7?动作最短长度1[2]2否右指针扩张-2[2,3]5否右指针扩张-3[2,3,1]6否右指针扩张-4[2,3,1,2]8是收缩左指针长度 445[3,1,2]6否右指针扩张46[3,1,2,4]10是收缩左指针长度 447[1,2,4]7是收缩左指针长度 338[2,4]6否右指针扩张39[2,4,3]9是收缩左指针长度 3310[4,3]7是收缩左指针长度 22最终得到最短长度为 2即子数组[4,3]与题目示例一致。源码实现解析仓库中的完整实现位于 leetcode/0209.Minimum-Size-Subarray-Sum/209. Minimum Size Subarray Sum.gopackage leetcode func minSubArrayLen(target int, nums []int) int { left, sum, res : 0, 0, len(nums)1 for right, v : range nums { sum v for sum target { res min(res, right-left1) sum - nums[left] left } } if res len(nums)1 { return 0 } return res } func min(a int, b int) int { if a b { return b } return a }逐行拆解这段代码的核心设计left, sum, res : 0, 0, len(nums)1left是窗口左边界sum维护当前窗口[left, right]的元素和res初始化为len(nums)1这是一个不可能达到的哨兵值用于区分找到了解与无解两种状态外层for right, v : range numsright每轮向右移动一步sum v将新元素纳入窗口实现窗口的扩张内层for sum target只要窗口和满足条件就尝试收缩先记录当前窗口长度right-left1并更新最小值再把nums[left]从和中减去、left。内层循环可能在多轮收缩后依然满足条件例如示例中[1,2,4]收缩为[2,4]后 sum 仍为 6 7 才停止因此必须用for而不是ifif res len(nums)1 { return 0 }如果遍历结束后res仍是哨兵值说明整个数组之和都小于target此时返回 0对应题目如果不存在返回 0的要求。这里有一个容易被忽略的边界细节因为题目保证数组元素全为正整数所以左指针永远不会超过右指针——每次内层收缩都从sum中扣除了一个正整数最多收缩到left right时窗口为空sum 为 0不可能出现left right的越界情形。若题目允许负数元素这种朴素滑动窗口就不成立了需要改造成前缀和 单调队列/二分等其它方案。测试用例与正确性验证仓库为本题配备了完整的表驱动测试见 leetcode/0209.Minimum-Size-Subarray-Sum/209. Minimum Size Subarray Sum_test.gofunc Test_Problem209(t *testing.T) { qs : []question209{ { para209{7, []int{2, 3, 1, 2, 4, 3}}, ans209{2}, }, { para209{100, []int{1, 2, 3, 4}}, ans209{0}, }, } ... for _, q : range qs { a, p : q.ans209, q.para209 got : minSubArrayLen(p.s, p.one) if got ! a.one { t.Fatalf(input: %v, expected: %v, got: %v, p, a.one, got) } } }测试用例覆盖了两类典型场景存在解s 7, nums [2,3,1,2,4,3]期望输出 2最短子数组[4,3]无解s 100, nums [1,2,3,4]整个数组和只有 10 小于 100期望输出 0用于验证哨兵值len(nums)1的兜底逻辑。在本地具备 Go 环境的机器上可进入该题解目录运行go test -v -run Test_Problem209仓库根目录的 gotest.sh 脚本也提供了批量跑测试的方式可供参考。该实现通过内层for循环在每次右指针移动后一次性完成所有可能的收缩保证每个元素至多被加入一次、移出一次这正是滑动窗口 O(n) 复杂度的来源。进阶O(n log n) 解法前缀和 二分查找题目 Follow up 要求尝试 O(n log n) 的解法。在正整数前提下可以借助前缀和数组的单调性配合二分查找实现预处理前缀和数组pre[i]表示nums[0..i-1]之和pre严格单调递增因为元素为正枚举子数组左端点i问题转化为找到最小的j i使得pre[j] - pre[i] s即pre[j] pre[i] s由于pre单调可以用二分查找在 O(log n) 时间内定位这个最小的j窗口长度为j - i枚举所有i取最小值总复杂度 O(n log n)。参考伪代码如下func minSubArrayLenBS(target int, nums []int) int { n : len(nums) pre : make([]int, n1) // pre[i] nums[0..i-1] 之和 for i : 1; i n; i { pre[i] pre[i-1] nums[i-1] } res : n 1 for i : 0; i n; i { // 在 pre[i1..n] 中二分查找第一个 pre[i]target 的位置 lo, hi : i1, n for lo hi { mid : (lo hi) / 2 if pre[mid] pre[i]target { hi mid } else { lo mid 1 } } if pre[lo] pre[i]target { res min(res, lo-i) } } if res n1 { return 0 } return res }两种解法的对比解法时间复杂度空间复杂度适用前提滑动窗口双指针O(n)O(1)元素全为正数前缀和 二分O(n log n)O(n)元素全为正数保证前缀和单调且允许 O(n) 额外空间实际刷题与面试中O(n) 的滑动窗口是首选O(n log n) 的二分方案更多用于印证你对有序结构 二分组合的掌握程度。值得一提的是如果把题目约束放宽到允许负数前缀和数组不再单调上述两种方案都会失效此时需要改用前缀和 哈希表/平衡树或前缀和 单调队列等更进阶的手段——这也是 209 题能延伸出多种变体的原因。总结LeetCode 209 是滑动窗口思想的典型代表其核心价值在于滑动窗口的伸缩节奏右指针扩张加元素内层循环收缩减元素每次移动都是 O(1) 的增量更新避免了重复计算子数组和哨兵值的巧妙使用用len(nums)1作为初始值天然区分有解与无解代码简洁且无歧义拓展思维的训练从 O(n) 到 O(n log n) 的 Follow up引导你建立单调性 二分的意识为后续遇到前缀和类题目打下基础。仓库中本题的 题解文档、滑动窗口实现 与 表驱动测试 三位一体是阅读源码、对照验证的最佳入口。掌握了本题的滑动窗口框架你可以顺带迁移到 76Minimum Window Substring、424Longest Repeating Character Replacement等同族题目上形成系统化的解题方法论。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode 209. Minimum Size Subarray Sum：Go 滑动窗口解法与 O(n log n) 拓展
LeetCode 209. Minimum Size Subarray SumGo 滑动窗口解法与 O(n log n) 拓展【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读LeetCode 209 是一道经典的滑动窗口Sliding Window入门题给定一个由正整数组成的数组和目标值 s需要找出和 ≥ s 的最短连续子数组。本篇文章以 LeetCode-Go 仓库中 0209.Minimum-Size-Subarray-Sum 的题解文档为核心结合仓库内完整的 Go 实现与单元测试逐行拆解双指针滑动窗口的原理、边界处理与复杂度分析并进一步推导题目要求的 O(n log n) 进阶解法前缀和 二分查找帮助你彻底掌握这一类最短/最长连续子数组满足某条件问题的通用套路。题目理解原题描述给定一个由 n 个正整数组成的数组nums和一个正整数s找出和 ≥s的最短连续子数组contiguous subarray的长度。如果不存在这样的子数组返回 0。示例 1输入: s 7, nums [2,3,1,2,4,3] 输出: 2 解释: 子数组 [4,3] 是满足和 ≥ 7 的最短连续子数组Follow up进阶要求如果你已经想出了 O(n) 的解法请尝试再实现一个时间复杂度为 O(n log n) 的解法。从题目描述可以提炼出三个关键约束数组元素全为正整数这是滑动窗口解法能够成立的前提正整数保证右指针扩张时窗口和单调不减左指针收缩时窗口和单调不增要求的是连续子数组因此不能排序必须保留元素原有的相对顺序求的是满足条件的最小长度一旦不存在解要返回 0 而不是某个默认值。题目大意给定一个整型数组和一个数字s找到数组中最短的一个连续子数组使得连续子数组的数字之和sum s返回最短连续子数组的长度。若整个数组之和都小于s则返回 0。解题思路滑动窗口双指针本题的官方推荐解法是滑动窗口。在窗口[i, j]之间不断往后移动如果当前窗口内总和小于s就扩大右边界j不断加入右边的值直到sum s此时记录窗口长度并尝试收缩左边界i不断缩小直到sum s此时右边界又可以继续往右移动重复上述过程。整个过程右指针只向右走一遍左指针也只向右走一遍因此整体时间复杂度为 O(n)。为了便于理解我们用示例s 7, nums [2,3,1,2,4,3]手工模拟一遍窗口的伸缩过程步骤窗口内容窗口和sum ≥ 7?动作最短长度1[2]2否右指针扩张-2[2,3]5否右指针扩张-3[2,3,1]6否右指针扩张-4[2,3,1,2]8是收缩左指针长度 445[3,1,2]6否右指针扩张46[3,1,2,4]10是收缩左指针长度 447[1,2,4]7是收缩左指针长度 338[2,4]6否右指针扩张39[2,4,3]9是收缩左指针长度 3310[4,3]7是收缩左指针长度 22最终得到最短长度为 2即子数组[4,3]与题目示例一致。源码实现解析仓库中的完整实现位于 leetcode/0209.Minimum-Size-Subarray-Sum/209. Minimum Size Subarray Sum.gopackage leetcode func minSubArrayLen(target int, nums []int) int { left, sum, res : 0, 0, len(nums)1 for right, v : range nums { sum v for sum target { res min(res, right-left1) sum - nums[left] left } } if res len(nums)1 { return 0 } return res } func min(a int, b int) int { if a b { return b } return a }逐行拆解这段代码的核心设计left, sum, res : 0, 0, len(nums)1left是窗口左边界sum维护当前窗口[left, right]的元素和res初始化为len(nums)1这是一个不可能达到的哨兵值用于区分找到了解与无解两种状态外层for right, v : range numsright每轮向右移动一步sum v将新元素纳入窗口实现窗口的扩张内层for sum target只要窗口和满足条件就尝试收缩先记录当前窗口长度right-left1并更新最小值再把nums[left]从和中减去、left。内层循环可能在多轮收缩后依然满足条件例如示例中[1,2,4]收缩为[2,4]后 sum 仍为 6 7 才停止因此必须用for而不是ifif res len(nums)1 { return 0 }如果遍历结束后res仍是哨兵值说明整个数组之和都小于target此时返回 0对应题目如果不存在返回 0的要求。这里有一个容易被忽略的边界细节因为题目保证数组元素全为正整数所以左指针永远不会超过右指针——每次内层收缩都从sum中扣除了一个正整数最多收缩到left right时窗口为空sum 为 0不可能出现left right的越界情形。若题目允许负数元素这种朴素滑动窗口就不成立了需要改造成前缀和 单调队列/二分等其它方案。测试用例与正确性验证仓库为本题配备了完整的表驱动测试见 leetcode/0209.Minimum-Size-Subarray-Sum/209. Minimum Size Subarray Sum_test.gofunc Test_Problem209(t *testing.T) { qs : []question209{ { para209{7, []int{2, 3, 1, 2, 4, 3}}, ans209{2}, }, { para209{100, []int{1, 2, 3, 4}}, ans209{0}, }, } ... for _, q : range qs { a, p : q.ans209, q.para209 got : minSubArrayLen(p.s, p.one) if got ! a.one { t.Fatalf(input: %v, expected: %v, got: %v, p, a.one, got) } } }测试用例覆盖了两类典型场景存在解s 7, nums [2,3,1,2,4,3]期望输出 2最短子数组[4,3]无解s 100, nums [1,2,3,4]整个数组和只有 10 小于 100期望输出 0用于验证哨兵值len(nums)1的兜底逻辑。在本地具备 Go 环境的机器上可进入该题解目录运行go test -v -run Test_Problem209仓库根目录的 gotest.sh 脚本也提供了批量跑测试的方式可供参考。该实现通过内层for循环在每次右指针移动后一次性完成所有可能的收缩保证每个元素至多被加入一次、移出一次这正是滑动窗口 O(n) 复杂度的来源。进阶O(n log n) 解法前缀和 二分查找题目 Follow up 要求尝试 O(n log n) 的解法。在正整数前提下可以借助前缀和数组的单调性配合二分查找实现预处理前缀和数组pre[i]表示nums[0..i-1]之和pre严格单调递增因为元素为正枚举子数组左端点i问题转化为找到最小的j i使得pre[j] - pre[i] s即pre[j] pre[i] s由于pre单调可以用二分查找在 O(log n) 时间内定位这个最小的j窗口长度为j - i枚举所有i取最小值总复杂度 O(n log n)。参考伪代码如下func minSubArrayLenBS(target int, nums []int) int { n : len(nums) pre : make([]int, n1) // pre[i] nums[0..i-1] 之和 for i : 1; i n; i { pre[i] pre[i-1] nums[i-1] } res : n 1 for i : 0; i n; i { // 在 pre[i1..n] 中二分查找第一个 pre[i]target 的位置 lo, hi : i1, n for lo hi { mid : (lo hi) / 2 if pre[mid] pre[i]target { hi mid } else { lo mid 1 } } if pre[lo] pre[i]target { res min(res, lo-i) } } if res n1 { return 0 } return res }两种解法的对比解法时间复杂度空间复杂度适用前提滑动窗口双指针O(n)O(1)元素全为正数前缀和 二分O(n log n)O(n)元素全为正数保证前缀和单调且允许 O(n) 额外空间实际刷题与面试中O(n) 的滑动窗口是首选O(n log n) 的二分方案更多用于印证你对有序结构 二分组合的掌握程度。值得一提的是如果把题目约束放宽到允许负数前缀和数组不再单调上述两种方案都会失效此时需要改用前缀和 哈希表/平衡树或前缀和 单调队列等更进阶的手段——这也是 209 题能延伸出多种变体的原因。总结LeetCode 209 是滑动窗口思想的典型代表其核心价值在于滑动窗口的伸缩节奏右指针扩张加元素内层循环收缩减元素每次移动都是 O(1) 的增量更新避免了重复计算子数组和哨兵值的巧妙使用用len(nums)1作为初始值天然区分有解与无解代码简洁且无歧义拓展思维的训练从 O(n) 到 O(n log n) 的 Follow up引导你建立单调性 二分的意识为后续遇到前缀和类题目打下基础。仓库中本题的 题解文档、滑动窗口实现 与 表驱动测试 三位一体是阅读源码、对照验证的最佳入口。掌握了本题的滑动窗口框架你可以顺带迁移到 76Minimum Window Substring、424Longest Repeating Character Replacement等同族题目上形成系统化的解题方法论。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
