和至少为 K 的最短子数组

和至少为 K 的最短子数组如何用前缀和与单调队列求解？

• 先构造前缀和数组 prefixSum, 问题变为求最小的 j - i 使 prefixSum[j] - prefixSum[i] >= k;
• 维护一个下标队列 queue, 队列中的前缀和严格递增;
• 对每个 j 依次做三步:
  • 队首满足 prefixSum[j] - prefixSum[queue[0]] >= k 时弹出队首并更新最短长度;
  • 队尾前缀和大于等于 prefixSum[j] 时弹出队尾;
  • 把 j 入队;

两个弹出操作各自为什么成立？

• 弹出队首: 之后的 j 只会更大, 这些 i 已不可能再产生更短的区间;
• 弹出队尾: 对之后的任意 j', 用 j 都比用队尾下标更短且更容易满足差值条件;
• 因此被弹出的下标永远不会再成为最优解;

和至少为 K 的最短子数组如何实现？

function shortestSubarray(nums: number[], k: number): number {
  const n = nums.length;
  const prefixSum = new Array(n + 1);
  prefixSum[0] = 0;
  for (let i = 1; i <= n; i++) {
    prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
  }

  let res = n + 1;
  const queue: number[] = [];
  for (let i = 0; i <= n; i++) {
    while (queue.length !== 0 && prefixSum[i] - prefixSum[queue[0]] >= k) {
      const index = queue.shift()!;
      res = Math.min(i - index, res);
    }
    while (queue.length !== 0 && prefixSum[i] <= prefixSum[queue[queue.length - 1]]) {
      queue.pop();
    }
    queue.push(i);
  }

  return res === n + 1 ? -1 : res;
}

和至少为 K 的最短子数组的复杂度是多少？

• 时间复杂度: O(n), 每个下标最多入队一次、出队一次;
• 空间复杂度: O(n);
• 限制: 元素含负数时前缀和不再单调, 不能用普通双指针替代;