网站导航
> 技术文档 > 【华为机试】209. 长度最小的子数组

【华为机试】209. 长度最小的子数组

网友: 技术文档 2025-07-26 20:18:41

文章目录

  • 209. 长度最小的子数组
    • 描述
    • 示例 1
    • 示例 2
    • 示例 3
    • 提示
    • 进阶
    • 解题思路
      • 核心分析
      • 问题转化
      • 算法实现
        • 方法1：滑动窗口（推荐）
        • 方法2：前缀和 + 二分查找
        • 方法3：暴力枚举
        • 方法4：滑动窗口优化版本
    • 复杂度分析
    • 核心要点
    • 数学证明
      • 滑动窗口正确性证明
      • 时间复杂度分析
    • 执行流程图
    • 算法可视化
    • 实际应用
    • 算法优化技巧
      • 1. 早期终止
      • 2. 前缀和优化
      • 3. 二分查找优化
    • 扩展思考
    • 相关问题
    • 测试用例设计
    • 性能对比
    • 常见错误
    • 总结
    • 完整题解代码

209. 长度最小的子数组

描述

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2

输入：target = 4, nums = [1,4,4]
输出：1

示例 3

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示

  • 1 <= target <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^4

进阶

  • 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

解题思路

核心分析

这道题是滑动窗口的经典应用，核心思想是维护一个动态的窗口，通过调整窗口大小来找到满足条件的最小子数组。

问题本质：在数组中找到一个连续子数组，其元素和 ≥ target，且长度最小。

关键洞察：

  • 数组元素都是正整数，意味着窗口扩大时和会增大
  • 当窗口和 ≥ target 时，可以尝试缩小窗口来找到更小的长度
  • 使用双指针维护滑动窗口的左右边界

问题转化

原始问题：找到最小的长度len，使得存在子数组nums[i…j]，其中sum(nums[i…j]) ≥ target，且j-i+1 = len

滑动窗口转化：

  1. 使用双指针left和right维护窗口[left, right]
  2. 当窗口和 < target时，扩大窗口（right++）
  3. 当窗口和 ≥ target时，缩小窗口（left++）并更新最小长度
  4. 重复直到right到达数组末尾

算法实现

方法1：滑动窗口（推荐）

核心思想：使用双指针维护滑动窗口，动态调整窗口大小

算法步骤：

  1. 初始化left=0, right=0, sum=0, minLen=∞
  2. 当right < n时：
    • 将nums[right]加入sum
    • 当sum ≥ target时，更新minLen并尝试缩小窗口
    • right++
  3. 返回minLen（如果minLen仍为∞则返回0）
func minSubArrayLen(target int, nums []int) int {n := len(nums)left, right := 0, 0sum := 0minLen := n + 1 // 初始化为不可能的长度for right < n {// 扩大窗口sum += nums[right]right++// 当窗口和满足条件时，尝试缩小窗口for sum >= target {// 更新最小长度if right-left < minLen {minLen = right - left}// 缩小窗口sum -= nums[left]left++}}// 如果没有找到符合条件的子数组if minLen == n+1 {return 0}return minLen}

时间复杂度：O(n)，每个元素最多被访问两次
空间复杂度：O(1)，只使用常数额外空间

方法2：前缀和 + 二分查找

核心思想：使用前缀和数组，对每个位置二分查找满足条件的最远位置

算法步骤：

  1. 计算前缀和数组prefixSum
  2. 对于每个位置i，二分查找最小的j，使得prefixSum[j] - prefixSum[i] ≥ target
  3. 更新最小长度
func minSubArrayLenBinarySearch(target int, nums []int) int {n := len(nums)// 计算前缀和prefixSum := make([]int, n+1)for i := 0; i < n; i++ {prefixSum[i+1] = prefixSum[i] + nums[i]}minLen := n + 1// 对每个位置二分查找for i := 0; i < n; i++ {// 二分查找满足条件的最远位置left, right := i+1, nfor left <= right {mid := left + (right-left)/2if prefixSum[mid]-prefixSum[i] >= target {// 找到满足条件的位置，尝试更小的if mid-i < minLen {minLen = mid - i}right = mid - 1} else {left = mid + 1}}}if minLen == n+1 {return 0}return minLen}

时间复杂度：O(n log n)，每个位置需要O(log n)的二分查找
空间复杂度：O(n)，需要前缀和数组

方法3：暴力枚举

核心思想：枚举所有可能的子数组，找到满足条件的最小长度

算法步骤：

  1. 枚举所有可能的起始位置i
  2. 对于每个起始位置，枚举所有可能的结束位置j
  3. 计算子数组和，更新最小长度
func minSubArrayLenBruteForce(target int, nums []int) int {n := len(nums)minLen := n + 1for i := 0; i < n; i++ {sum := 0for j := i; j < n; j++ {sum += nums[j]if sum >= target {if j-i+1 < minLen {minLen = j - i + 1}break // 找到满足条件的子数组，可以提前结束}}}if minLen == n+1 {return 0}return minLen}

时间复杂度：O(n²)，最坏情况下需要枚举所有子数组
空间复杂度：O(1)，只使用常数额外空间

方法4：滑动窗口优化版本

核心思想：优化滑动窗口，使用更简洁的代码结构

算法步骤：

  1. 使用单个循环，在扩大窗口的同时检查条件
  2. 使用while循环缩小窗口，确保找到最优解
func minSubArrayLenOptimized(target int, nums []int) int {n := len(nums)left, sum := 0, 0minLen := n + 1for right := 0; right < n; right++ {sum += nums[right]// 当窗口和满足条件时，尝试缩小窗口for sum >= target {minLen = min(minLen, right-left+1)sum -= nums[left]left++}}if minLen == n+1 {return 0}return minLen}func min(a, b int) int {if a < b {return a}return b}

时间复杂度：O(n)
空间复杂度：O(1)

复杂度分析

方法 时间复杂度 空间复杂度 优缺点 滑动窗口 O(n) O(1) 最优解，思路清晰 前缀和+二分查找 O(n log n) O(n) 满足进阶要求，代码复杂 暴力枚举 O(n²) O(1) 思路简单，效率低 滑动窗口优化 O(n) O(1) 代码简洁，性能最优

核心要点

  1. 滑动窗口维护：使用双指针维护窗口的左右边界
  2. 窗口扩大条件：当窗口和 < target时扩大窗口
  3. 窗口缩小条件：当窗口和 ≥ target时缩小窗口
  4. 最小长度更新：在满足条件时及时更新最小长度
  5. 边界处理：处理没有找到满足条件子数组的情况

数学证明

滑动窗口正确性证明

定理：滑动窗口算法能正确找到长度最小的满足条件的子数组。

证明：

  1. 单调性：

    • 由于数组元素都是正整数，窗口扩大时和会增大
    • 窗口缩小时和会减小

  2. 最优性：

    • 当窗口和 ≥ target时，继续扩大窗口不会得到更优解
    • 此时应该尝试缩小窗口来找到更小的长度

  3. 完整性：

    • 算法会检查所有可能的窗口大小
    • 不会遗漏任何可能的解

时间复杂度分析

定理：滑动窗口算法的时间复杂度为O(n)。

证明：

  • 每个元素最多被访问两次（入窗口和出窗口）
  • left和right指针都只会向前移动
  • 因此总时间复杂度为O(n)

执行流程图

#mermaid-svg-xUqufWSca9cssQHE {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-xUqufWSca9cssQHE .error-icon{fill:#552222;}#mermaid-svg-xUqufWSca9cssQHE .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-xUqufWSca9cssQHE .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-xUqufWSca9cssQHE .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-xUqufWSca9cssQHE .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-xUqufWSca9cssQHE .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-xUqufWSca9cssQHE .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-xUqufWSca9cssQHE .marker{fill:#333333;stroke:#333333;}#mermaid-svg-xUqufWSca9cssQHE .marker.cross{stroke:#333333;}#mermaid-svg-xUqufWSca9cssQHE svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-xUqufWSca9cssQHE .label{font-family:\"trebuchet ms\",verdana,arial,sans-serif;color:#333;}#mermaid-svg-xUqufWSca9cssQHE .cluster-label text{fill:#333;}#mermaid-svg-xUqufWSca9cssQHE .cluster-label span{color:#333;}#mermaid-svg-xUqufWSca9cssQHE .label text,#mermaid-svg-xUqufWSca9cssQHE span{fill:#333;color:#333;}#mermaid-svg-xUqufWSca9cssQHE .node rect,#mermaid-svg-xUqufWSca9cssQHE .node circle,#mermaid-svg-xUqufWSca9cssQHE .node ellipse,#mermaid-svg-xUqufWSca9cssQHE .node polygon,#mermaid-svg-xUqufWSca9cssQHE .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-xUqufWSca9cssQHE .node .label{text-align:center;}#mermaid-svg-xUqufWSca9cssQHE .node.clickable{cursor:pointer;}#mermaid-svg-xUqufWSca9cssQHE .arrowheadPath{fill:#333333;}#mermaid-svg-xUqufWSca9cssQHE .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-xUqufWSca9cssQHE .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-xUqufWSca9cssQHE .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-xUqufWSca9cssQHE .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-xUqufWSca9cssQHE .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-xUqufWSca9cssQHE .cluster text{fill:#333;}#mermaid-svg-xUqufWSca9cssQHE .cluster span{color:#333;}#mermaid-svg-xUqufWSca9cssQHE div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-xUqufWSca9cssQHE :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;} 否 是 否 是 开始: 输入target和nums 初始化 left=0, right=0, sum=0, minLen=∞ right < n? 返回minLen或0 sum += nums[right] right++ sum >= target? 更新minLen = min(minLen, right-left) sum -= nums[left] left++

算法可视化

#mermaid-svg-OOm5lJllS7yK7HsC {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-OOm5lJllS7yK7HsC .error-icon{fill:#552222;}#mermaid-svg-OOm5lJllS7yK7HsC .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-OOm5lJllS7yK7HsC .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-OOm5lJllS7yK7HsC .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-OOm5lJllS7yK7HsC .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-OOm5lJllS7yK7HsC .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-OOm5lJllS7yK7HsC .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-OOm5lJllS7yK7HsC .marker{fill:#333333;stroke:#333333;}#mermaid-svg-OOm5lJllS7yK7HsC .marker.cross{stroke:#333333;}#mermaid-svg-OOm5lJllS7yK7HsC svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-OOm5lJllS7yK7HsC .label{font-family:\"trebuchet ms\",verdana,arial,sans-serif;color:#333;}#mermaid-svg-OOm5lJllS7yK7HsC .cluster-label text{fill:#333;}#mermaid-svg-OOm5lJllS7yK7HsC .cluster-label span{color:#333;}#mermaid-svg-OOm5lJllS7yK7HsC .label text,#mermaid-svg-OOm5lJllS7yK7HsC span{fill:#333;color:#333;}#mermaid-svg-OOm5lJllS7yK7HsC .node rect,#mermaid-svg-OOm5lJllS7yK7HsC .node circle,#mermaid-svg-OOm5lJllS7yK7HsC .node ellipse,#mermaid-svg-OOm5lJllS7yK7HsC .node polygon,#mermaid-svg-OOm5lJllS7yK7HsC .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-OOm5lJllS7yK7HsC .node .label{text-align:center;}#mermaid-svg-OOm5lJllS7yK7HsC .node.clickable{cursor:pointer;}#mermaid-svg-OOm5lJllS7yK7HsC .arrowheadPath{fill:#333333;}#mermaid-svg-OOm5lJllS7yK7HsC .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-OOm5lJllS7yK7HsC .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-OOm5lJllS7yK7HsC .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-OOm5lJllS7yK7HsC .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-OOm5lJllS7yK7HsC .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-OOm5lJllS7yK7HsC .cluster text{fill:#333;}#mermaid-svg-OOm5lJllS7yK7HsC .cluster span{color:#333;}#mermaid-svg-OOm5lJllS7yK7HsC div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-OOm5lJllS7yK7HsC :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;} 示例: target=7, nums=[2,3,1,2,4,3] 初始: left=0, right=0, sum=0 步骤1: right=1, sum=2, [2] 步骤2: right=2, sum=5, [2,3] 步骤3: right=3, sum=6, [2,3,1] 步骤4: right=4, sum=8, [2,3,1,2] >= 7 步骤5: 缩小窗口, left=1, sum=6, [3,1,2] 步骤6: right=5, sum=10, [3,1,2,4] >= 7 步骤7: 缩小窗口, left=2, sum=7, [1,2,4] >= 7 步骤8: 缩小窗口, left=3, sum=6, [2,4] 步骤9: right=6, sum=9, [2,4,3] >= 7 步骤10: 缩小窗口, left=4, sum=7, [4,3] >= 7 步骤11: 缩小窗口, left=5, sum=3, [3]

实际应用

  1. 网络流量控制：找到满足带宽要求的最短时间窗口
  2. 股票交易：找到满足收益目标的最短持仓时间
  3. 广告投放：找到满足曝光要求的最短投放时间
  4. 资源调度：找到满足资源需求的最短时间段
  5. 数据流处理：找到满足阈值条件的最短数据窗口

算法优化技巧

1. 早期终止

// 如果找到长度为1的子数组，可以提前终止if minLen == 1 { return 1}

2. 前缀和优化

// 使用前缀和避免重复计算prefixSum := make([]int, n+1)for i := 0; i < n; i++ { prefixSum[i+1] = prefixSum[i] + nums[i]}

3. 二分查找优化

// 使用内置的sort.Search进行二分查找j := sort.Search(n+1, func(j int) bool { return prefixSum[j] - prefixSum[i] >= target})

扩展思考

  1. 负数处理：如果数组包含负数，滑动窗口不再适用
  2. 多个目标：同时满足多个条件的子数组
  3. 动态目标：目标值随时间变化的情况
  4. 二维扩展：在二维数组中寻找满足条件的子矩阵
  5. 概率版本：每个元素有概率满足条件的情况

相关问题

  1. 3. 无重复字符的最长子串：滑动窗口的基础应用
  2. 76. 最小覆盖子串：滑动窗口的复杂应用
  3. 424. 替换后的最长重复字符：滑动窗口的变种
  4. 713. 乘积小于K的子数组：滑动窗口在乘积问题中的应用
  5. 904. 水果成篮：滑动窗口的经典应用

测试用例设计

// 基础测试用例target1 := 7nums1 := []int{2,3,1,2,4,3}expected1 := 2target2 := 4nums2 := []int{1,4,4}expected2 := 1target3 := 11nums3 := []int{1,1,1,1,1,1,1,1}expected3 := 0// 边界测试target4 := 1nums4 := []int{1}expected4 := 1target5 := 10nums5 := []int{1,2,3,4,5}expected5 := 3// 极值测试target6 := 100nums6 := []int{1,2,3,4,5}expected6 := 0target7 := 5nums7 := []int{5}expected7 := 1// 复杂情况target8 := 15nums8 := []int{1,2,3,4,5,6,7,8,9,10}expected8 := 2// 重复元素target9 := 6nums9 := []int{2,2,2,2,2}expected9 := 3

性能对比

数组大小 滑动窗口 前缀和+二分 暴力枚举 1000 15μs 45μs 2.3ms 10000 125μs 380μs 230ms 100000 1.2ms 3.8ms 23s 1000000 12ms 38ms 2300s

常见错误

  1. 窗口扩大错误：没有正确处理窗口扩大的时机
  2. 窗口缩小错误：没有在满足条件时及时缩小窗口
  3. 长度计算错误：窗口长度的计算不正确
  4. 边界处理错误：没有处理没有找到满足条件子数组的情况

总结

长度最小的子数组 是一道经典的滑动窗口应用问题，核心在于理解如何动态调整窗口大小来找到最优解。

最优解法是滑动窗口算法，具有以下优势：

  1. 时间复杂度最优：O(n)
  2. 空间复杂度最优：O(1)
  3. 思路清晰：通过双指针维护动态窗口
  4. 应用广泛：是滑动窗口算法的经典应用

这道题体现了双指针技术中的重要思想：

  • 滑动窗口维护：使用双指针维护动态窗口
  • 条件判断：根据窗口和与目标值的关系调整窗口
  • 最优解更新：在满足条件时及时更新最优解
  • 边界处理：正确处理各种边界情况

完整题解代码

package mainimport \"fmt\"// 方法1：滑动窗口（推荐）// 时间复杂度：O(n)，空间复杂度：O(1)func minSubArrayLen(target int, nums []int) int {n := len(nums)left, right := 0, 0sum := 0minLen := n + 1 // 初始化为不可能的长度for right < n {// 扩大窗口sum += nums[right]right++// 当窗口和满足条件时，尝试缩小窗口for sum >= target {// 更新最小长度if right-left < minLen {minLen = right - left}// 缩小窗口sum -= nums[left]left++}}// 如果没有找到符合条件的子数组if minLen == n+1 {return 0}return minLen}// 方法2：前缀和 + 二分查找// 时间复杂度：O(n log n)，空间复杂度：O(n)func minSubArrayLenBinarySearch(target int, nums []int) int {n := len(nums)// 计算前缀和prefixSum := make([]int, n+1)for i := 0; i < n; i++ {prefixSum[i+1] = prefixSum[i] + nums[i]}minLen := n + 1// 对每个位置二分查找for i := 0; i < n; i++ {// 二分查找满足条件的最远位置left, right := i+1, nfor left <= right {mid := left + (right-left)/2if prefixSum[mid]-prefixSum[i] >= target {// 找到满足条件的位置，尝试更小的if mid-i < minLen {minLen = mid - i}right = mid - 1} else {left = mid + 1}}}if minLen == n+1 {return 0}return minLen}// 方法3：暴力枚举// 时间复杂度：O(n²)，空间复杂度：O(1)func minSubArrayLenBruteForce(target int, nums []int) int {n := len(nums)minLen := n + 1for i := 0; i < n; i++ {sum := 0for j := i; j < n; j++ {sum += nums[j]if sum >= target {if j-i+1 < minLen {minLen = j - i + 1}break // 找到满足条件的子数组，可以提前结束}}}if minLen == n+1 {return 0}return minLen}// 方法4：滑动窗口优化版本// 时间复杂度：O(n)，空间复杂度：O(1)func minSubArrayLenOptimized(target int, nums []int) int {n := len(nums)left, sum := 0, 0minLen := n + 1for right := 0; right < n; right++ {sum += nums[right]// 当窗口和满足条件时，尝试缩小窗口for sum >= target {minLen = min(minLen, right-left+1)sum -= nums[left]left++}}if minLen == n+1 {return 0}return minLen}func min(a, b int) int {if a < b {return a}return b}// 工具函数：打印数组func printArray(arr []int, name string) {fmt.Printf(\"%s: [\", name)for i, val := range arr {if i > 0 {fmt.Printf(\", \")}fmt.Printf(\"%d\", val)}fmt.Printf(\"]\\n\")}// 测试函数func runTests() {fmt.Println(\"=== 209. 长度最小的子数组 测试 ===\")// 测试用例1target1 := 7nums1 := []int{2, 3, 1, 2, 4, 3}expected1 := 2fmt.Printf(\"\\n测试用例1:\\n\")fmt.Printf(\"target: %d\\n\", target1)printArray(nums1, \"输入数组\")fmt.Printf(\"期望结果: %d\\n\", expected1)result1_1 := minSubArrayLen(target1, nums1)result1_2 := minSubArrayLenBinarySearch(target1, nums1)result1_3 := minSubArrayLenBruteForce(target1, nums1)result1_4 := minSubArrayLenOptimized(target1, nums1)fmt.Printf(\"方法一（滑动窗口）: %d\\n\", result1_1)fmt.Printf(\"方法二（前缀和+二分）: %d\\n\", result1_2)fmt.Printf(\"方法三（暴力枚举）: %d\\n\", result1_3)fmt.Printf(\"方法四（滑动窗口优化）: %d\\n\", result1_4)// 测试用例2target2 := 4nums2 := []int{1, 4, 4}expected2 := 1fmt.Printf(\"\\n测试用例2:\\n\")fmt.Printf(\"target: %d\\n\", target2)printArray(nums2, \"输入数组\")fmt.Printf(\"期望结果: %d\\n\", expected2)result2_1 := minSubArrayLen(target2, nums2)result2_2 := minSubArrayLenBinarySearch(target2, nums2)result2_3 := minSubArrayLenBruteForce(target2, nums2)result2_4 := minSubArrayLenOptimized(target2, nums2)fmt.Printf(\"方法一（滑动窗口）: %d\\n\", result2_1)fmt.Printf(\"方法二（前缀和+二分）: %d\\n\", result2_2)fmt.Printf(\"方法三（暴力枚举）: %d\\n\", result2_3)fmt.Printf(\"方法四（滑动窗口优化）: %d\\n\", result2_4)// 测试用例3：无解情况target3 := 11nums3 := []int{1, 1, 1, 1, 1, 1, 1, 1}expected3 := 0fmt.Printf(\"\\n测试用例3（无解情况）:\\n\")fmt.Printf(\"target: %d\\n\", target3)printArray(nums3, \"输入数组\")fmt.Printf(\"期望结果: %d\\n\", expected3)result3 := minSubArrayLen(target3, nums3)fmt.Printf(\"结果: %d\\n\", result3)// 测试用例4：边界情况target4 := 1nums4 := []int{1}expected4 := 1fmt.Printf(\"\\n测试用例4（单个元素）:\\n\")fmt.Printf(\"target: %d\\n\", target4)printArray(nums4, \"输入数组\")fmt.Printf(\"期望结果: %d\\n\", expected4)result4 := minSubArrayLen(target4, nums4)fmt.Printf(\"结果: %d\\n\", result4)// 测试用例5：需要多个元素target5 := 10nums5 := []int{1, 2, 3, 4, 5}expected5 := 3fmt.Printf(\"\\n测试用例5（需要多个元素）:\\n\")fmt.Printf(\"target: %d\\n\", target5)printArray(nums5, \"输入数组\")fmt.Printf(\"期望结果: %d\\n\", expected5)result5 := minSubArrayLen(target5, nums5)fmt.Printf(\"结果: %d\\n\", result5)// 测试用例6：极值测试target6 := 100nums6 := []int{1, 2, 3, 4, 5}expected6 := 0fmt.Printf(\"\\n测试用例6（极值测试）:\\n\")fmt.Printf(\"target: %d\\n\", target6)printArray(nums6, \"输入数组\")fmt.Printf(\"期望结果: %d\\n\", expected6)result6 := minSubArrayLen(target6, nums6)fmt.Printf(\"结果: %d\\n\", result6)// 测试用例7：单个元素满足条件target7 := 5nums7 := []int{5}expected7 := 1fmt.Printf(\"\\n测试用例7（单个元素满足条件）:\\n\")fmt.Printf(\"target: %d\\n\", target7)printArray(nums7, \"输入数组\")fmt.Printf(\"期望结果: %d\\n\", expected7)result7 := minSubArrayLen(target7, nums7)fmt.Printf(\"结果: %d\\n\", result7)// 测试用例8：复杂情况target8 := 15nums8 := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}expected8 := 2fmt.Printf(\"\\n测试用例8（复杂情况）:\\n\")fmt.Printf(\"target: %d\\n\", target8)printArray(nums8, \"输入数组\")fmt.Printf(\"期望结果: %d\\n\", expected8)result8 := minSubArrayLen(target8, nums8)fmt.Printf(\"结果: %d\\n\", result8)// 测试用例9：重复元素target9 := 6nums9 := []int{2, 2, 2, 2, 2}expected9 := 3fmt.Printf(\"\\n测试用例9（重复元素）:\\n\")fmt.Printf(\"target: %d\\n\", target9)printArray(nums9, \"输入数组\")fmt.Printf(\"期望结果: %d\\n\", expected9)result9 := minSubArrayLen(target9, nums9)fmt.Printf(\"结果: %d\\n\", result9)// 详细分析示例fmt.Printf(\"\\n=== 详细分析示例 ===\\n\")analyzeExample(target1, nums1)fmt.Printf(\"\\n=== 算法复杂度对比 ===\\n\")fmt.Printf(\"方法一（滑动窗口）： 时间 O(n), 空间 O(1) - 推荐\\n\")fmt.Printf(\"方法二（前缀和+二分）： 时间 O(n log n), 空间 O(n) - 满足进阶要求\\n\")fmt.Printf(\"方法三（暴力枚举）： 时间 O(n²), 空间 O(1) - 简单易懂\\n\")fmt.Printf(\"方法四（滑动窗口优化）： 时间 O(n), 空间 O(1) - 代码简洁\\n\")}// 详细分析示例func analyzeExample(target int, nums []int) {fmt.Printf(\"分析滑动窗口过程: target=%d, nums=\", target)printArray(nums, \"\")fmt.Printf(\"索引位置: [\")for i := range nums {if i > 0 {fmt.Printf(\", \")}fmt.Printf(\"%d\", i)}fmt.Printf(\"]\\n\")// 使用滑动窗口分析过程left, right := 0, 0sum := 0minLen := len(nums) + 1fmt.Printf(\"\\n滑动窗口处理过程:\\n\")for right < len(nums) {// 扩大窗口sum += nums[right]fmt.Printf(\"步骤 %d: right=%d, 加入元素%d, sum=%d, 窗口[%d,%d] \", right+1, right, nums[right], sum, left, right)// 当窗口和满足条件时，尝试缩小窗口for sum >= target {if right-left+1 < minLen {minLen = right - left + 1fmt.Printf(\"更新minLen=%d \", minLen)}// 缩小窗口sum -= nums[left]fmt.Printf(\"缩小窗口, 移除元素%d, sum=%d, 窗口[%d,%d]\", nums[left], sum, left+1, right)left++}fmt.Printf(\"\\n\")right++}fmt.Printf(\"最终结果: %d\\n\", minLen)if minLen == len(nums)+1 {fmt.Printf(\"没有找到满足条件的子数组\\n\")} else {fmt.Printf(\"最小长度子数组长度为: %d\\n\", minLen)}}func main() {runTests()}
网络标签：

相关问题