209.长度最小的子数组

具体见代码随想录

（版本一）滑动窗口法
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 的长度。
   • left 和 right 是滑动窗口的左右指针，初始都为 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 的最短子数组长度。