网站如何定位,网站建设需要的设备,旅游小网站怎样做精不做全,静态页面是什么意思1.题目分析#xff1a;
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] #xff0c;并返回其长度。如果不存在符合条件的子数组#xff0c;返回 0 。
示例 …1.题目分析
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] 并返回其长度。如果不存在符合条件的子数组返回 0 。
示例 1
输入target 7, nums [2,3,1,2,4,3]
输出2
解释子数组
[4,3]是该条件下的长度最小的子数组。1.找出连续子数组 2.最短长度 3.特殊情况数组总和小于target返回零 2.算法分析
方法一暴力枚举时间复杂度是O(n^3)
设置两个指针分别表示子数组的开始和子数组的结束两层for循环最后求子数组总和一个while自己在脑子想想跑不过我就不画图写代码了哈。
方法二在暴力枚举的方法上做出改进--滑动窗口还是用了双指针和单调性全是正数会越加越大让两个指针同向移动来实现优化 滑动窗口步骤1.进入窗口 2.判断窗口 3.退出窗口 例一图示target 7, nums [2,3,1,2,4,3] 3.代码编写
public static int minSubArrayLen(int target, int[] nums) {int sum0;int countInteger.MAX_VALUE;int left0;int right0;for(left0,right0;rightnums.length;right){sumnums[right];//进窗口while (sumtarget)//判断{countMath.min(count,right-left1);sum-nums[left];//出窗口}}if(countInteger.MAX_VALUE){return 0;}return count;}
