线性动态规划：统计和至少为K的最短子数组长度
字数 2474 2025-12-23 10:26:10

线性动态规划：统计和至少为K的最短子数组长度

题目描述

给定一个整数数组 nums 和一个整数 K，要求找到一个 连续子数组，使得其元素之和至少为 K，并返回该子数组的 最小长度。
如果不存在这样的子数组，则返回 0。

示例

  • 输入：nums = [2, -1, 2, 1], K = 3
    输出：2
    解释：子数组 [2, 1] 的和为 3，长度为 2（子数组 [2, -1, 2] 和也为 3，但长度更长）。

  • 输入：nums = [1, 2], K = 4
    输出：0
    解释：没有子数组的和至少为 4。

逐步讲解

第一步：问题分析

我们需要找到最短的连续子数组，其和至少为 K。
最直观的方法是枚举所有子数组，计算它们的和与长度，找到满足条件的最短长度。
但这样时间复杂度是 O(n²)，对于大规模数据会超时。
我们的目标是利用 前缀和 和 单调队列 思想，将复杂度优化到 O(n)。

第二步：前缀和数组

定义前缀和数组 prefixSum[i] 表示 nums[0] + nums[1] + ... + nums[i-1]，即前 i 个元素的和。
为了方便处理，我们通常设 prefixSum[0] = 0，那么：

prefixSum[i] = prefixSum[i-1] + nums[i-1]

这样，子数组 nums[i..j] 的和可以表示为：

sum(i, j) = prefixSum[j+1] - prefixSum[i]

第三步：问题转化

我们想找到满足条件的最短子数组 (i, j)，其中 i ≤ j，使得：

prefixSum[j+1] - prefixSum[i] ≥ K

即：

prefixSum[i] ≤ prefixSum[j+1] - K

对于每个 j，我们要找 最小的 j - i，也就是在 i 的范围 0..j 中，找到满足上述不等式的最大 prefixSum[i] 对应的最小 i。

第四步：单调队列思想

我们维护一个 单调递增队列（存储下标 i），队列中的下标对应的 prefixSum 值是递增的。
遍历每个 j（实际上是遍历 prefixSum 的索引），对于当前的 j：

  1. 如果队列头（最小的 prefixSum[i]）满足： 
    prefixSum[j] - prefixSum[queue.front()] ≥ K
    那么以 queue.front() 为起点的子数组满足条件，我们更新最小长度，并弹出队头（因为它已经是最优解，后面不会再使用它了）。
  2. 为了保持队列单调递增，我们在将当前下标 j 加入队列前，弹出所有 prefixSum[queue.back()] ≥ prefixSum[j] 的元素，因为对于后面的 j'，prefixSum[j] 更小且下标更大（更优）。

第五步：算法步骤

  1. 计算前缀和数组 prefixSum。
  2. 初始化一个双端队列 deque，存放前缀和的下标。
  3. 初始化最短长度 minLen = n+1（一个不可能的大值）。
  4. 遍历 j 从 0 到 n（prefixSum 的下标）：
    • 步骤 A：如果队列非空，且 prefixSum[j] - prefixSum[deque.front()] ≥ K，则：
      • 计算当前子数组长度 j - deque.front()，更新 minLen。
      • 弹出队头（因为已经使用过，对于更大的 j，它不会产生更短的子数组）。
      • 重复此步骤直到条件不满足。
    • 步骤 B：维护队列单调递增：
      • 当队列非空且 prefixSum[deque.back()] ≥ prefixSum[j] 时，弹出队尾（因为 j 更靠后且 prefixSum 更小，更优）。
      • 将 j 加入队尾。
  5. 如果 minLen 仍为 n+1，返回 0；否则返回 minLen。

第六步：示例推演

以 nums = [2, -1, 2, 1], K = 3 为例：

  1. 前缀和 prefixSum = [0, 2, 1, 3, 4]（长度 n+1）。
  2. 初始化队列 deque = [], minLen = 5。
  3. 遍历：
    • j=0：队列空，直接加入 0 → deque=[0]。
    • j=1：prefixSum[1]=2，prefixSum[1]-prefixSum[0]=2 <3，不更新；维护队列：prefixSum[0]=0 ≤ 2，加入 1 → deque=[0,1]。
    • j=2：prefixSum[2]=1，队头 0：1-0=1<3；队头 1：1-2=-1<3，不更新。维护队列：弹出 1（因为 prefixSum[1]=2 ≥ 1），加入 2 → deque=[0,2]。
    • j=3：prefixSum[3]=3，队头 0：3-0=3≥3，长度=3，minLen=3，弹出 0。现在队头 2：3-1=2<3。维护队列：加入 3 → deque=[2,3]。
    • j=4：prefixSum[4]=4，队头 2：4-1=3≥3，长度=2，minLen=2，弹出 2。队头 3：4-3=1<3。维护队列：加入 4 → deque=[3,4]。
  4. 最终 minLen=2。

第七步：复杂度分析

  • 时间复杂度：O(n)，每个下标最多进出队列一次。
  • 空间复杂度：O(n)，用于存储前缀和和队列。

第八步：边界情况

  • 数组为空：直接返回 0。
  • 所有数都是负数且 K>0：可能无解，返回 0。
  • K ≤ 0：最短长度为 1（只要数组非空，因为任意一个元素自身就满足和至少为 K），但注意如果 K=0，最短长度可以是 0（空子数组），但题目通常要求非空子数组，所以按 K>0 处理即可。

总结

本题的关键在于 前缀和 和 单调队列 的结合，通过维护一个单调递增的队列，快速找到对于每个右端点 j 的最优左端点 i，从而在 O(n) 时间内解决问题。
这种技巧适用于“和至少为K的最短子数组”一类问题，是滑动窗口与单调栈/队列思想的经典应用。

线性动态规划：统计和至少为K的最短子数组长度 题目描述 给定一个整数数组 nums 和一个整数 K ，要求找到一个 连续子数组 ，使得其元素之和至少为 K ，并返回该子数组的 最小长度 。 如果不存在这样的子数组，则返回 0 。 示例 输入： nums = [2, -1, 2, 1] , K = 3 输出： 2 解释：子数组 [2, 1] 的和为 3，长度为 2（子数组 [2, -1, 2] 和也为 3，但长度更长）。 输入： nums = [1, 2] , K = 4 输出： 0 解释：没有子数组的和至少为 4。 逐步讲解 第一步：问题分析 我们需要找到最短的连续子数组，其和至少为 K 。 最直观的方法是枚举所有子数组，计算它们的和与长度，找到满足条件的最短长度。 但这样时间复杂度是 O(n²) ，对于大规模数据会超时。 我们的目标是利用 前缀和 和 单调队列 思想，将复杂度优化到 O(n) 。 第二步：前缀和数组 定义前缀和数组 prefixSum[i] 表示 nums[0] + nums[1] + ... + nums[i-1] ，即前 i 个元素的和。 为了方便处理，我们通常设 prefixSum[0] = 0 ，那么： 这样，子数组 nums[i..j] 的和可以表示为： 第三步：问题转化 我们想找到满足条件的最短子数组 (i, j) ，其中 i ≤ j ，使得： 即： 对于每个 j ，我们要找 最小的 j - i ，也就是在 i 的范围 0..j 中，找到满足上述不等式的最大 prefixSum[i] 对应的最小 i 。 第四步：单调队列思想 我们维护一个 单调递增队列 （存储下标 i ），队列中的下标对应的 prefixSum 值是递增的。 遍历每个 j （实际上是遍历 prefixSum 的索引），对于当前的 j ： 如果队列头（最小的 prefixSum[i] ）满足： 那么以 queue.front() 为起点的子数组满足条件，我们更新最小长度，并弹出队头（因为它已经是最优解，后面不会再使用它了）。 为了保持队列单调递增，我们在将当前下标 j 加入队列前，弹出所有 prefixSum[queue.back()] ≥ prefixSum[j] 的元素，因为对于后面的 j' ， prefixSum[j] 更小且下标更大（更优）。 第五步：算法步骤 计算前缀和数组 prefixSum 。 初始化一个双端队列 deque ，存放前缀和的下标。 初始化最短长度 minLen = n+1 （一个不可能的大值）。 遍历 j 从 0 到 n （ prefixSum 的下标）： 步骤 A ：如果队列非空，且 prefixSum[j] - prefixSum[deque.front()] ≥ K ，则： 计算当前子数组长度 j - deque.front() ，更新 minLen 。 弹出队头（因为已经使用过，对于更大的 j ，它不会产生更短的子数组）。 重复此步骤直到条件不满足。 步骤 B ：维护队列单调递增： 当队列非空且 prefixSum[deque.back()] ≥ prefixSum[j] 时，弹出队尾（因为 j 更靠后且 prefixSum 更小，更优）。 将 j 加入队尾。 如果 minLen 仍为 n+1 ，返回 0 ；否则返回 minLen 。 第六步：示例推演 以 nums = [2, -1, 2, 1] , K = 3 为例： 前缀和 prefixSum = [0, 2, 1, 3, 4] （长度 n+1）。 初始化队列 deque = [] , minLen = 5 。 遍历： j=0 ：队列空，直接加入 0 → deque=[0] 。 j=1 ： prefixSum[1]=2 ， prefixSum[1]-prefixSum[0]=2 <3，不更新；维护队列： prefixSum[0]=0 ≤ 2 ，加入 1 → deque=[0,1] 。 j=2 ： prefixSum[2]=1 ，队头 0 ： 1-0=1<3 ；队头 1 ： 1-2=-1<3 ，不更新。维护队列：弹出 1 （因为 prefixSum[1]=2 ≥ 1 ），加入 2 → deque=[0,2] 。 j=3 ： prefixSum[3]=3 ，队头 0 ： 3-0=3≥3 ，长度=3， minLen=3 ，弹出 0 。现在队头 2 ： 3-1=2<3 。维护队列：加入 3 → deque=[2,3] 。 j=4 ： prefixSum[4]=4 ，队头 2 ： 4-1=3≥3 ，长度=2， minLen=2 ，弹出 2 。队头 3 ： 4-3=1<3 。维护队列：加入 4 → deque=[3,4] 。 最终 minLen=2 。 第七步：复杂度分析 时间复杂度： O(n) ，每个下标最多进出队列一次。 空间复杂度： O(n) ，用于存储前缀和和队列。 第八步：边界情况 数组为空：直接返回 0 。 所有数都是负数且 K>0 ：可能无解，返回 0 。 K ≤ 0 ：最短长度为 1（只要数组非空，因为任意一个元素自身就满足和至少为 K ），但注意如果 K=0 ，最短长度可以是 0（空子数组），但题目通常要求非空子数组，所以按 K>0 处理即可。 总结 本题的关键在于 前缀和 和 单调队列 的结合，通过维护一个单调递增的队列，快速找到对于每个右端点 j 的最优左端点 i ，从而在 O(n) 时间内解决问题。 这种技巧适用于“和至少为K的最短子数组”一类问题，是滑动窗口与单调栈/队列思想的经典应用。