LeetCode.209.长度最小的子数组
题目描述：
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的
子数组
[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0
输入输出实例：
思路：首先介绍一个暴力解法（时间复杂度较高没有通过），我们使用length和start两个变量用来表示子数组长度和起始下标，然后我们慢慢增加length长度和start，直到找到满足sum(nums[start:start + length]) >= target这一条件我们return length 。循环结束后我们return 0。但是这个方法时间复杂度较高，我们进行优化。
class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:length = 1start = 0while length <= len(nums):while start + length <= len(nums):if sum(nums[start:start + length]) >= target :return lengthstart += 1start = 0length += 1return 0优化后：使用滑动窗口， left和right为我们的左右区间，current_sum为该区间的值的总和，我们先从下标为0的值开始加，right往后走，直到区间的总和>=target，这时我们再对左侧进行删减以减少区间长度，left往后移，最小长度我们使用min_length = min(min_length,right - left + 1)实现，当前长度与原来最小长度取最小值。这样最后我们left和right围成的区间是满足条件的且长度最小的，由于我们刚开始min_length设置一个很大的值，如果最后依旧是这个值说明我们没有找到满足条件的区间return 0，否则return min_length
class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:n = len(nums)current_sum = 0left = 0min_length = float('inf')for right in range(n):current_sum += nums[right]while current_sum >= target :min_length = min(min_length,right - left + 1)current_sum -= nums[left]left += 1return min_length if min_length != float('inf') else 0