当前位置: 首页> 教育> 大学 > 209.长度最小的子数组

209.长度最小的子数组

时间:2025/7/11 4:34:33来源:https://blog.csdn.net/weixin_43837522/article/details/141227621 浏览次数:1次

在这里插入图片描述
具体见代码随想录

(版本一)滑动窗口法
class Solution:def minSubArrayLen(self, s: int, nums: List[int]) -> int:l = len(nums)left = 0right = 0min_len = float('inf')cur_sum = 0 #当前的累加值while right < l:cur_sum += nums[right]while cur_sum >= s: # 当前累加值大于目标值min_len = min(min_len, right - left + 1)cur_sum -= nums[left]left += 1right += 1return min_len if min_len != float('inf') else 0

这段代码实现了一个滑动窗口算法,目的是找到一个最小的连续子数组,其和大于或等于给定值 s。以下是对每个部分的详细解释:

  1. 类和方法定义

    class Solution:def minSubArrayLen(self, s: int, nums: List[int]) -> int:
    

    这里定义了一个名为 Solution 的类,包含一个方法 minSubArrayLen,该方法接收一个整数 s 和一个整数列表 nums,返回满足条件的最小子数组的长度。

  2. 初始化变量

        l = len(nums)left = 0right = 0min_len = float('inf')cur_sum = 0
    
    • l 是输入数组 nums 的长度。
    • leftright 是滑动窗口的左右指针,初始都为 0。
    • min_len 用于记录当前找到的满足条件的最小子数组长度,初始设置为正无穷(float('inf'))。
    • cur_sum 用于存储当前窗口内的元素和,初始为 0。
  3. 主循环

        while right < l:cur_sum += nums[right]
    

    循环遍历数组,通过增加 right 指针来扩大窗口并累加当前窗口的和。

  4. 内部循环

            while cur_sum >= s:min_len = min(min_len, right - left + 1)cur_sum -= nums[left]left += 1
    

    当当前和 cur_sum 大于或等于 s 时,进入内部循环:

    • 更新 min_len,计算当前子数组的长度(right - left + 1),并与 min_len 比较,取较小值。
    • 减去 left 指向的元素,缩小窗口,更新 cur_sum
    • left 指针向右移动。
  5. 结束条件

            right += 1
    

    增加 right 指针,继续扩大窗口。

  6. 返回结果

        return min_len if min_len != float('inf') else 0
    

    如果 min_len 仍然是正无穷,说明没有找到满足条件的子数组,返回 0;否则,返回 min_len

总结

该算法的时间复杂度为 O(n),空间复杂度为 O(1),高效地找到和大于或等于 s 的最短子数组长度。

关键字:209.长度最小的子数组

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: