【每日演算法】長度最小的子數組
題目描述
這是 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
