1. 题目:
给定一个含有 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
2. 我的代码:
class Solution: def minSubArrayLen(self, target: int, nums: List[int]) -> int: fast_i = 0 slow_i = 0 # 记录目前总和 sum_now = 0 len_min = 100000000 # 滑动窗口 for fast_i in range(len(nums)): sum_now += nums[fast_i] while sum_now >= target: len_min = min(len_min, fast_i - slow_i + 1) sum_now -= nums[slow_i] slow_i += 1 if len_min == 100000000: return 0 return len_min
这种求区间内东西的题型可以使用滑动窗口,滑动窗口其实就是快慢指针中间夹的部分。因为要求值,所以为了防止再去遍历滑动窗口内的元素,所以,定义了数字总一步一步地加和。
快指针的范围是从0
到len(nums) - 1
,然后当总和大于等于target
时慢指针向右缩短,并且记录此时的最小长度(作为最小长度的起始值,可以定义一个非常大的数字)。
如果最小长度还是初始值,则说明没有最小长度的子数组,因此返回0