小黑day5那拉提空中草原上午因下雨关闭改去河谷草原，下午薰衣草基地，入住伊宁江苏酒店附近吃当地特色羊肉串的leetcode之旅:209. 长度最小的子数组

小黑代码

class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:# 数组长度n = len(nums)# 定义双指针head = 0tail = 0# 中间变量sum_ = 0# 结果变量min_ = n + 1# 开始迭代 while head < n:# 尾部指针右移while tail < n and sum_ < target:sum_ += nums[tail]tail += 1# 记录长度if sum_ >= target and min_ > tail - head:min_ = tail - headsum_ -= nums[head]head += 1return min_ if min_ != n + 1 else 0

在这里插入图片描述

小黑根据思路自己尝试前缀和二分法

class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:# 数组长度n = len(nums)# 计算前缀和arr = [0] + [nums[0]] * nfor i in range(1, n+1):arr[i] = arr[i-1] + nums[i-1]# 结果变量res = n + 1# 开始进行二分查找print(arr)for i in range(n+1):if arr[i] < target:continuel = self.left_search(arr[:i], arr[i] - target)length = i - l + 1 if arr[i] - target < arr[l] else i - lif length < res:res = lengthreturn res if res != n + 1 else 0def left_search(self, arr, target):# 初始化双指针left = 0right = len(arr) - 1while left <= right:mid = (left + right) // 2if arr[mid] < target:left = mid + 1else:right = mid - 1return left

在这里插入图片描述

前缀和二分法

class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:# 数组长度n = len(nums)# 构造前缀和数组arr = [0]for i in range(n):arr.append(nums[i]+arr[i])# 开始进行二分查找大于等于arr[i]+target的最近左位置# 结果变量res = n + 1for i in range(n):end = self.left_search(arr,i+1, target+arr[i])if end == n + 1:continuelength = end - iif length < res:res = lengthreturn res if res != n + 1 else 0def left_search(self, arr, start, target):n = len(arr)# 定义左右指针start = startend = n - 1while start <= end:mid = (start + end) // 2if arr[mid] < target:start = mid + 1else:end = mid - 1return start

在这里插入图片描述

双指针法

class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:# 数组长度n = len(nums)# 中间变量sum_ = 0# 头尾指针head = 0tail = 0# 结果变量res = n + 1# 开始双指针迭代while tail < n:sum_ += nums[tail]tail += 1while sum_ >= target:if tail - head < res:res = tail - headsum_ -= nums[head]head += 1return res if res != n + 1 else 0