【leetcode】209. 长度最小的子数组

题目

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

代码

1. 暴力求解

暴力求解: 18 / 21
思路：双循环

class Solution(object):def minSubArrayLen(self, target, nums):""":type target: int:type nums: List[int]:rtype: int"""# 暴力求解: 18 / 21 min_len = float("inf")for i in range(len(nums)):cur_sum = 0for j in range(i, len(nums)):cur_sum += nums[j]if cur_sum >= target:min_len = min(min_len, j -i +1)breakreturn min_len if min_len != float('inf') else 0

2. 滑动窗口

**思路：**根据滑动窗口算窗口下的总和，如果大于target，则窗口左边+1

class Solution(object):def minSubArrayLen(self, target, nums):""":type target: int:type nums: List[int]:rtype: int"""# 滑动窗口l = len(nums)left = 0right = 0sum = 0min_lenth = float("inf")while right < l:sum += nums[right]# 当前累计值大于等于targetwhile sum >= target:min_lenth = min(min_lenth, right - left + 1)sum -= nums[left]left += 1right += 1return min_lenth if min_lenth != float("inf") else 0