https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/
一、题目解析
给定整数数组 nums（元素可正可负）和整数 k，找出和 ≥ k 的最短非空连续子数组，返回其长度。不存在则返回 -1。
以 nums = [-28,81,-20,28,-29], k = 89 为例：子数组 [81,-20,28] 和为 89，长度 3，是满足条件的最短子数组。[81] 和 81 < 89，不满足。[81,-20,28,-29] 和 60 < 89，虽然更长也不满足。
由于存在负数，前缀和不再单调递增。普通滑动窗口失效——扩大窗口时和可能变小，缩小窗口时和可能变大，无法用双指针简单地维护。
二、前缀和 + 单调队列思路
2.1 前缀和转化
构建前缀和数组 preSum，其中 preSum[i] 表示 nums[0..i-1] 的和。子数组 nums[i..j] 的和 = preSum[j+1] - preSum[i]。问题转化为：找两个索引 x < y，使得 preSum[y] - preSum[x] ≥ k，且 y - x 最小。
2.2 单调递增队列
维护一个存索引的单调递增队列（按 preSum 值递增）。遍历 preSum，对每个位置 i：
去头（找答案）：如果 preSum[i] - preSum[队头] ≥ k，说明队头作为起点已经满足条件。记录长度 i - 队头，弹出队头继续检查——因为队头匹配当前 i 已经是最短的，未来更远的 i 只会更长，队头已完成使命。
去尾（维护单调）：如果 preSum[队尾] ≥ preSum[i]，弹出队尾。队尾的 preSum 值更大且索引更靠前，属于"又老又弱"——未来元素与当前 i 配对，不仅更容易满足 preSum - preSum[i] ≥ k，而且距离更短。队尾被永久淘汰。
队列始终保持 preSum 值递增、索引递增。每个索引入队一次、出队一次。
2.3 完整推演
以 nums = [-28,81,-20,28,-29], k = 89 推一遍。preSum = [0, -28, 53, 33, 61, 32]。
i=0, preSum=0：入队。队列：[0]
i=1, preSum=-28：队头 0，-28-0=-28 < 89，不触发去头。队尾 preSum[0]=0 ≥ -28，弹 0。入队 1。队列：[1]
i=2, preSum=53：队头 1，53-(-28)=81 < 89。队尾 preSum[1]=-28 < 53，不入队头部操作。入队 2。队列：[1, 2]
i=3, preSum=33：队头 1，33-(-28)=61 < 89。队尾 preSum[2]=53 ≥ 33，弹 2。新队尾 preSum[1]=-28 < 33。入队 3。队列：[1, 3]
i=4, preSum=61：队头 1，61-(-28)=89 ≥ 89！ans=4-1=3。弹 1。新队头 3，61-33=28 < 89。队尾 preSum[3]=33 < 61。入队 4。队列：[3, 4]
i=5, preSum=32：队头 3，32-33=-1 < 89。队尾 preSum[4]=61 ≥ 32，弹 4。新队尾 preSum[3]=33 ≥ 32，弹 3。入队 5。队列：[5]
ans = 3。对应子数组 [81,-20,28]。
三、代码实现
class Solution { public int shortestSubarray(int[] nums, int k) { // 构建前缀和数组 preSum[i] = nums[0..i-1] 的和 int[] preSum = new int[nums.length + 1]; for (int i = 1; i <= nums.length; i++) { preSum[i] = preSum[i - 1] + nums[i - 1]; } // 单调递增队列，存前缀和索引，preSum 值递增 Deque<Integer> queue = new ArrayDeque<>(); int ans = Integer.MAX_VALUE; for (int i = 0; i < preSum.length; i++) { // 去头：队头作为起点已满足 preSum[i] - preSum[队头] >= k while (!queue.isEmpty() && preSum[i] - preSum[queue.peekFirst()] >= k) { ans = Math.min(ans, i - queue.peekFirst()); queue.pollFirst(); // 队头使命完成，弹出 } // 去尾：队尾 preSum 更大且索引更靠前，被当前 i 永久淘汰 while (!queue.isEmpty() && preSum[queue.peekLast()] >= preSum[i]) { queue.pollLast(); } // 入队 queue.addLast(i); } return ans == Integer.MAX_VALUE ? -1 : ans; }}时间复杂度 O(n)，每个索引至多入队一次、出队一次。空间复杂度 O(n)，队列最多存 n 个索引。
本文由 AgentPlanFlow 生成