具体见代码随想录
(版本一)滑动窗口法
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
。以下是对每个部分的详细解释:
-
类和方法定义:
class Solution:def minSubArrayLen(self, s: int, nums: List[int]) -> int:
这里定义了一个名为
Solution
的类,包含一个方法minSubArrayLen
,该方法接收一个整数s
和一个整数列表nums
,返回满足条件的最小子数组的长度。 -
初始化变量:
l = len(nums)left = 0right = 0min_len = float('inf')cur_sum = 0
l
是输入数组nums
的长度。left
和right
是滑动窗口的左右指针,初始都为 0。min_len
用于记录当前找到的满足条件的最小子数组长度,初始设置为正无穷(float('inf')
)。cur_sum
用于存储当前窗口内的元素和,初始为 0。
-
主循环:
while right < l:cur_sum += nums[right]
循环遍历数组,通过增加
right
指针来扩大窗口并累加当前窗口的和。 -
内部循环:
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
指针向右移动。
- 更新
-
结束条件:
right += 1
增加
right
指针,继续扩大窗口。 -
返回结果:
return min_len if min_len != float('inf') else 0
如果
min_len
仍然是正无穷,说明没有找到满足条件的子数组,返回 0;否则,返回min_len
。
总结
该算法的时间复杂度为 O(n),空间复杂度为 O(1),高效地找到和大于或等于 s
的最短子数组长度。