网站空间提供商响应式网站什么用

网站空间提供商,响应式网站什么用,三亚网址之家,wordpress 页脚代码862. 和至少为 K 的最短子数组 问题描述 给你一个整数数组 nums 和一个整数 k#xff0c;找出 和至少为 k 的最短非空子数组#xff0c;并返回该子数组的长度。如果不存在这样的子数组#xff0c;返回 -1。 子数组是数组中连续的元素序列。 示例#xff1a; 输入: nums [1…862. 和至少为 K 的最短子数组问题描述给你一个整数数组nums和一个整数k找出和至少为 k 的最短非空子数组并返回该子数组的长度。如果不存在这样的子数组返回-1。子数组是数组中连续的元素序列。示例输入:nums[1],k1输出:1输入:nums[1,2],k4输出:-1输入:nums[2,-1,2],k3输出:3解释:子数组[2,-1,2]的和为3长度为3输入:nums[84,-37,32,40,95],k167输出:3解释:子数组[32,40,95]的和为167长度为3算法思路前缀和 单调双端队列核心子数组和问题通常用前缀和解决sum[i..j] prefix[j1] - prefix[i]需要找到j i使得prefix[j] - prefix[i] k且j - i最小单调队列如果prefix[i] prefix[j]且i j那么i永远不会成为最优解的左端点j比i更靠右子数组更短且前缀和更小更容易满足 k的条件维护一个前缀和单调递增的队列为什么需要单调队列普通滑动窗口无法处理负数窗口收缩条件不明确暴力枚举是 O(n²)对于 n10⁵ 会超时单调队列将时间复杂度优化到 O(n)代码实现importjava.util.*;classSolution{/** * 找到和至少为K的最短子数组长度 * 使用前缀和 单调双端队列 * * param nums 输入数组可能包含负数 * param k 目标和 * return 最短子数组长度不存在返回-1 */publicintshortestSubarray(int[]nums,intk){intnnums.length;// 前缀和数组prefix[0] 0, prefix[i] nums[0] ... nums[i-1]long[]prefixnewlong[n1];for(inti0;in;i){prefix[i1]prefix[i]nums[i];}// 使用双端队列存储前缀和数组的索引// 队列中的索引对应的前缀和是单调递增的DequeIntegerdequenewLinkedList();intminLengthInteger.MAX_VALUE;// 遍历所有可能的右端点对应prefix数组的索引1到nfor(intj0;jn;j){// 检查队列头部是否有满足条件的左端点// prefix[j] - prefix[i] k prefix[i] prefix[j] - kwhile(!deque.isEmpty()prefix[j]-prefix[deque.peekFirst()]k){intideque.pollFirst();minLengthMath.min(minLength,j-i);}// 维护队列的单调性从尾部移除前缀和大于等于prefix[j]的索引// prefix[j]更靠右且前缀和更小所以之前的索引不可能成为最优解while(!deque.isEmpty()prefix[deque.peekLast()]prefix[j]){deque.pollLast();}// 将当前索引j加入队列deque.offerLast(j);}returnminLengthInteger.MAX_VALUE?-1:minLength;}}算法分析时间复杂度O(n)每个索引最多入队和出队一次总共 2n 次操作线性时间空间复杂度O(n)前缀和数组O(n)双端队列最坏情况下 O(n)算法过程1nums [2,-1,2], k 3前缀和计算nums: [2, -1, 2] prefix: [0, 2, 1, 3] indices: 0 1 2 3单调队列j0prefix[0]0队列为空直接加入deque [0]j1prefix[1]2检查队首2 - 0 2 3不满足条件维护单调性prefix[0]0 2无需移除加入队列deque [0,1]j2prefix[2]1检查队首1 - 0 1 3不满足条件维护单调性prefix[1]2 1移除索引1现在deque [0]prefix[0]0 1加入索引2deque [0,2]j3prefix[3]3检查队首3 - 0 3 3更新minLength min(∞, 3-0) 3移除索引0deque [2]再次检查队首3 - 1 2 3停止维护单调性prefix[2]1 3加入索引3deque [2,3]结果3测试用例publicclassMain{publicstaticvoidmain(String[]args){SolutionsolutionnewSolution();// 测试用例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// 测试用例7k为负数int[]nums7{-1,2,-1};System.out.println(Test 7: solution.shortestSubarray(nums7,-1));// 1 (单个-1)// 测试用例8边界情况 - k0int[]nums8{-1,-2,-3};System.out.println(Test 8: solution.shortestSubarray(nums8,0));// 1 (任何非空子数组)// 测试用例9大数组int[]nums9newint[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}}关键点前缀和prefix[0] 0处理从数组开头开始的子数组sum[i..j] prefix[j1] - prefix[i]单调队列队首用于找到满足条件的最优左端点队尾维护前缀和的单调递增性每个元素最多入队出队一次保证O(n)时间负数负数会导致前缀和减少破坏单调性单调队列通过移除无用的左端点来处理这种情况常见问题为什么需要单调递增的前缀和队列对于相同的右端点前缀和更小的左端点更容易满足 k的条件且位置更靠右子数组更短。为什么从队尾移除前缀和更大的元素假设i j且prefix[i] prefix[j]那么i永远不会比j更优j更靠右且前缀和更小。为什么使用双端队列而不是普通队列需要从两端进行操作从队首移除满足条件的元素从队尾移除破坏单调性的元素。