【每日算法】长度最小的子数组
题目描述
这是 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 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5
分析题目要求
字符串或数组找到满足条件的连续区间的问题可以想到的使用:滑动窗口的方法去解决。
在数组中使用滑动窗口的有出有进的，则需使用双端队列的方式可以在O(1)时间内完成。
定义一个队列，记录窗口内的元素，还需要一个变量记录窗口内元素的总和，因为要计算窗口内元素和与target进行比较。
代码实现
import collections
class Solution(object):
def minSubArrayLen(self, target, nums):
q=collections.deque()#记录窗口内的元素索引号
t=0#窗口内的元素的总和
res=float("inf")#记录结果,默认最大值
for i,v in enumerate(nums):
# print(i,v,q,t)
q.append(i)
t+=v
while t>=target:#窗口内的元素和满足条件，则从左侧逐个移除，找到最小的
res=min(res,q[-1]-q[0]+1)
if res==1:
return res
t-=nums[q.popleft()]#移除左侧的元素
# print(q,t)
return 0 if res==float("inf") else res
版权声明：本文为hitechr原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。