209.长度最小的子数组

2023.6.1
这道题的关键是滑动窗口法，滑动窗口法应设定好窗口左侧的右移条件与窗口右侧的移动条件
本例中先初始化好用到的各种值
循环的终止条件是滑动窗口右侧超出列表的范围
走来
cur_sum += nums[right]
是将cur_sum的值更新为当前滑动窗口[left,right]的值之和
接着通过内循环判断滑动窗口左侧要向右走多少（这是因为如果num[right]值很大，此时右侧添加进来一个值，需要左侧吐出去好几个值才能重新将cur_sum缩小到<target）
内循环中左侧每吐出一个一个left += 1
内循环结束时[left,right]的值之和恰好小于target
此时right+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

为什么滑动窗口法的时间复杂度是n，虽然是双循环结构，但实际上每个元素被纳入滑动窗口和吐出滑动窗口时各执行了一次，相当于每个元素一定被执行2次，因此O(2n) ⇒ O(n)

暴力解法
就是通过双循环得到所有可能的子列表，然后判断每个子列表是否符合条件，最后找到最短的子列表
这玩意执行直接超出时间限制

class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:l = len(nums)min_ = l + 1for i in range(l):for j in range(i,l):temp = nums[i:j+1]if sum(temp) >= target:min_ = min(min_, len(temp))return min_ if min_ != l + 1 else 0

总共循环1 + 2 + 3 + … + n = (n^2 + n)/2，因此时间复杂度为O(n^2)