晋城市城乡建设局网站,网络设计的约束要素是什么,百度seo排名规则,做网站的客户哪里找题目描述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的子数组
[numsl, numsl1, ..., numsr-1, numsr] #xff0c;并返回其长度。如果不存在符合条件的子数组#xff0c;返回 0 。
输入输出示例
输入…题目描述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的子数组
[numsl, numsl1, ..., numsr-1, numsr] 并返回其长度。如果不存在符合条件的子数组返回 0 。
输入输出示例
输入target 7, nums [2,3,1,2,4,3]
输出2
解释子数组 [4,3] 是该条件下的长度最小的子数组。 解决方案
方式一滑动窗口
算法思想
定义两个指针 start 和 end 分别表示子数组滑动窗口窗口的开始位置和结束位置维护变量 sum 存储子数组中的元素和即从 nums[start] 到 nums[end] 的元素和。
初始状态下start 和 end 都指向下标 0sum 的值为 0。
每一轮迭代将 nums[end] 加到 sum如果 sum≥s则更新子数组的最小长度此时子数组的长度是 end−start1然后将 nums[start] 从 sum 中减去并将 start 右移直到 sum
实现代码
class Solution {public int minSubArrayLen(int target, int[] nums) {int nnums.length;if(n0){return 0;}int ansInteger.MAX_VALUE;int start0,end0;//窗口的左边界和右边界int sum0;//窗口的元素和while(endn){//向右滑动sumnums[end];//当窗口内的元素和大于等于目标值缩小窗口while(sumtarget){ansMath.min(ans,end-start1);sum-nums[start];start;}//否则扩大窗口end;}//考虑达不到目标值的情况return ansInteger.MAX_VALUE?0:ans;}
}
复杂度分析
时间复杂度O(n)其中 n 是数组的长度。指针 start 和 end 最多各移动 n 次。
空间复杂度O(1)。
