算法题 和至少为 K 的最短子数组

862. 和至少为 K 的最短子数组

问题描述

给你一个整数数组nums和一个整数k，找出和至少为 k 的最短非空子数组，并返回该子数组的长度。如果不存在这样的子数组，返回-1。

子数组是数组中连续的元素序列。

示例：

输入:nums=[1],k=1输出:1

输入:nums=[1,2],k=4输出:-1

输入:nums=[2,-1,2],k=3输出:3解释:子数组[2,-1,2]的和为3，长度为3

输入:nums=[84,-37,32,40,95],k=167输出:3解释:子数组[32,40,95]的和为167，长度为3

算法思路

前缀和 + 单调双端队列：

1. 核心：

   • 子数组和问题通常用前缀和解决：sum[i..j] = prefix[j+1] - prefix[i]
   • 需要找到j > i使得prefix[j] - prefix[i] >= k，且j - i最小

2. 单调队列：

   • 如果prefix[i] >= prefix[j]且i < j，那么i永远不会成为最优解的左端点
   • j比i更靠右（子数组更短），且前缀和更小（更容易满足>= k的条件）
   • 维护一个前缀和单调递增的队列

3. 为什么需要单调队列？

   • 普通滑动窗口无法处理负数（窗口收缩条件不明确）
   • 暴力枚举是 O(n²)，对于 n=10⁵ 会超时
   • 单调队列将时间复杂度优化到 O(n)

代码实现

importjava.util.*;classSolution{/** * 找到和至少为K的最短子数组长度 * 使用前缀和 + 单调双端队列 * * @param nums 输入数组（可能包含负数） * @param k 目标和 * @return 最短子数组长度，不存在返回-1 */publicintshortestSubarray(int[]nums,intk){intn=nums.length;// 前缀和数组，prefix[0] = 0, prefix[i] = nums[0] + ... + nums[i-1]long[]prefix=newlong[n+1];for(inti=0;i<n;i++){prefix[i+1]=prefix[i]+nums[i];}// 使用双端队列存储前缀和数组的索引// 队列中的索引对应的前缀和是单调递增的Deque<Integer>deque=newLinkedList<>();intminLength=Integer.MAX_VALUE;// 遍历所有可能的右端点（对应prefix数组的索引1到n）for(intj=0;j<=n;j++){// 检查队列头部：是否有满足条件的左端点// prefix[j] - prefix[i] >= k => prefix[i] <= prefix[j] - kwhile(!deque.isEmpty()&&prefix[j]-prefix[deque.peekFirst()]>=k){inti=deque.pollFirst();minLength=Math.min(minLength,j-i);}// 维护队列的单调性：从尾部移除前缀和大于等于prefix[j]的索引// prefix[j]更靠右且前缀和更小，所以之前的索引不可能成为最优解while(!deque.isEmpty()&&prefix[deque.peekLast()]>=prefix[j]){deque.pollLast();}// 将当前索引j加入队列deque.offerLast(j);}returnminLength==Integer.MAX_VALUE?-1:minLength;}}

算法分析

• 时间复杂度：O(n)
  • 每个索引最多入队和出队一次
  • 总共 2n 次操作，线性时间
• 空间复杂度：O(n)
  • 前缀和数组：O(n)
  • 双端队列：最坏情况下 O(n)

算法过程

1：nums = [2,-1,2], k = 3

前缀和计算：

nums: [2, -1, 2] prefix: [0, 2, 1, 3] indices: 0 1 2 3

单调队列：

1. j=0：prefix[0]=0

   • 队列为空，直接加入
   • deque = [0]

2. j=1：prefix[1]=2

   • 检查队首：2 - 0 = 2 < 3，不满足条件
   • 维护单调性：prefix[0]=0 <= 2，无需移除
   • 加入队列：deque = [0,1]

3. j=2：prefix[2]=1

   • 检查队首：1 - 0 = 1 < 3，不满足条件
   • 维护单调性：prefix[1]=2 > 1，移除索引1
   • 现在deque = [0]，prefix[0]=0 <= 1，加入索引2
   • deque = [0,2]

4. j=3：prefix[3]=3

   • 检查队首：3 - 0 = 3 >= 3
     • 更新：minLength = min(∞, 3-0) = 3
     • 移除索引0，deque = [2]
   • 再次检查队首：3 - 1 = 2 < 3，停止
   • 维护单调性：prefix[2]=1 <= 3，加入索引3
   • deque = [2,3]

结果：3

测试用例

publicclassMain{publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：单个元素int[]nums1={1};System.out.println("Test 1: "+solution.shortestSubarray(nums1,1));// 1// 测试用例2：无解int[]nums2={1,2};System.out.println("Test 2: "+solution.shortestSubarray(nums2,4));// -1// 测试用例3：包含负数int[]nums3={2,-1,2};System.out.println("Test 3: "+solution.shortestSubarray(nums3,3));// 3// 测试用例4：复杂情况int[]nums4={84,-37,32,40,95};System.out.println("Test 4: "+solution.shortestSubarray(nums4,167));// 3// 测试用例5：全正数int[]nums5={1,2,3,4,5};System.out.println("Test 5: "+solution.shortestSubarray(nums5,11));// 3 ([3,4,5])// 测试用例6：全负数（无解）int[]nums6={-1,-2,-3};System.out.println("Test 6: "+solution.shortestSubarray(nums6,1));// -1// 测试用例7：k为负数int[]nums7={-1,2,-1};System.out.println("Test 7: "+solution.shortestSubarray(nums7,-1));// 1 (单个-1)// 测试用例8：边界情况 - k=0int[]nums8={-1,-2,-3};System.out.println("Test 8: "+solution.shortestSubarray(nums8,0));// 1 (任何非空子数组)// 测试用例9：大数组int[]nums9=newint[100000];Arrays.fill(nums9,1);System.out.println("Test 9: "+solution.shortestSubarray(nums9,50000));// 50000// 测试用例10：交替正负int[]nums10={1,-1,1,-1,1};System.out.println("Test 10: "+solution.shortestSubarray(nums10,1));// 1// 测试用例11：需要整个数组int[]nums11={1,1,1,1,1};System.out.println("Test 11: "+solution.shortestSubarray(nums11,5));// 5}}

关键点

1. 前缀和：

   • prefix[0] = 0处理从数组开头开始的子数组
   • sum[i..j] = prefix[j+1] - prefix[i]

2. 单调队列：

   • 队首：用于找到满足条件的最优左端点
   • 队尾：维护前缀和的单调递增性
   • 每个元素最多入队出队一次，保证O(n)时间

3. 负数：

   • 负数会导致前缀和减少，破坏单调性
   • 单调队列通过移除"无用"的左端点来处理这种情况

常见问题

1. 为什么需要单调递增的前缀和队列？
   对于相同的右端点，前缀和更小的左端点更容易满足>= k的条件，且位置更靠右（子数组更短）。

2. 为什么从队尾移除前缀和更大的元素？
   假设i < j且prefix[i] >= prefix[j]，那么i永远不会比j更优，j更靠右且前缀和更小。

3. 为什么使用双端队列而不是普通队列？
   需要从两端进行操作：从队首移除满足条件的元素，从队尾移除破坏单调性的元素。