'''

思路参考:https://github.com/Shellbye/Shellbye.github.io/issues/41
Time: O(N^2) TLE 

Brute Force + preSum 思路:
在Brute Force的基础上,加入一个PreSum来记忆化记忆一下到i为止的和,方便与之后直接调用

注意的事项就是要给preSum多预留一个位置,和DP类似,用来处理一些edge case,比如array总长就一个

Input: A = [1], K = 1
Output: 1

这个例子如果用 preSum[j] - preSum[i] 而不预留位置, preSum则为[1] ,由于两个位置重叠,减后的0
应该是给与额外的preSum位置,preSum则为[0, 1] 这样及时相减也能够得到1。 (1 - 0)
另外就是i和j的for循环分别多走一位,为了匹配多出来的一位preSum

'''
class Solution(object):
 def shortestSubarray(self, nums, target):
 preSum = [0]
 globalMin = float('inf')
 
 for num in nums:
 preSum.append(preSum[-1] + num)
 
 for i in range(len(nums) + 1):
 for j in range(i, len(nums) + 1):
 if preSum[j] - preSum[i] >= target:
 globalMin = min(globalMin, j - i) 
 
 return globalMin if globalMin != float('inf') else -1

'''
Time: O(N)
Space: O(N)


两个While Loop

第一个While Loop用于滑动窗口的中的,移动左边指针的操作
当preSum[i]减去queue里面最左边,也就是queue里面最小的index的时候(因为queue里存的是index,所以是升序排序的,queue[0]就可以理解为最小的数)
 如果满足超过target大小,我们保存在globalMin并且可以开始移动左边的指针了,所以这里queue.popleft掉了最左边的指针。


第二个While Loop用来删掉负数
 如果在preSum的数组里面,当前的preSum[i]要大于之前加进去的数的话,比如preSum[2] = 100, preSum[3] = 50, 说明从2-3的过程中,sum小了50,所以是加到了-50,加了一个负数。
 我们为了求取最小的subarray,负数的就要果断移除
'''
from collections import deque
class Solution(object):
 def shortestSubarray(self, nums, target):
 globalMin = float('inf')
 preSum = [0]
 for num in nums:
 preSum.append(preSum[-1] + num)
 
 queue = deque()
 for i in range(len(nums) + 1):
 while queue and preSum[i] - preSum[queue[0]] >= target: 
 globalMin = min(globalMin, i - queue.popleft()) 
 
 while queue and preSum[queue[-1]] >= preSum[i]:
 queue.pop()
 queue.append(i)
 return globalMin if globalMin != float('inf') else -1