class Solution {
public:
int shortestSubarray(vector<int>& nums, int k) {
}
};
862. 和至少为 K 的最短子数组
给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。
子数组 是数组中 连续 的一部分。
示例 1：
输入：nums = [1], k = 1 输出：1
示例 2：
输入：nums = [1,2], k = 4 输出：-1
示例 3：
输入：nums = [2,-1,2], k = 3 输出：3
提示：
1 <= nums.length <= 105-105 <= nums[i] <= 1051 <= k <= 109原站题解
python3 解法, 执行用时: 368 ms, 内存消耗: 25.5 MB, 提交时间: 2022-10-26 09:59:32
class Solution:
def shortestSubarray(self, nums: List[int], k: int) -> int:
ans = inf
cur_s = 0
q = deque([(0, -1)])
for i, x in enumerate(nums):
cur_s += x # 计算前缀和
while q and cur_s - q[0][0] >= k:
ans = min(ans, i - q.popleft()[1]) # 优化一
while q and q[-1][0] >= cur_s:
q.pop() # 优化二
q.append((cur_s, i))
return ans if ans < inf else -1
python3 解法, 执行用时: 384 ms, 内存消耗: 25.8 MB, 提交时间: 2022-10-26 09:54:15
class Solution:
def shortestSubarray(self, nums: List[int], k: int) -> int:
preSumArr = [0]
res = len(nums) + 1
for num in nums:
preSumArr.append(preSumArr[-1] + num)
q = deque()
for i, curSum in enumerate(preSumArr):
while q and curSum - preSumArr[q[0]] >= k:
res = min(res, i - q.popleft())
while q and preSumArr[q[-1]] >= curSum:
q.pop()
q.append(i)
return res if res < len(nums) + 1 else -1