怎么用织梦系统建一个网站,dede后台网站地图怎么做,免费网络电话试用,做石材的一般用什么网站给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续
子数组 [numsl, numsl1, ..., numsr-1, numsr] #xff0c;并返回其长度。如果不存在符合条件的子数组#xff0c;返回 0 。 示例 1#xff1a;
输入1, ..., numsr-1, numsr] 并返回其长度。如果不存在符合条件的子数组返回 0 。 示例 1
输入target 7, nums [2,3,1,2,4,3]
输出2
解释子数组 [4,3] 是该条件下的长度最小的子数组。示例 2
输入target 4, nums [1,4,4]
输出1示例 3
输入target 11, nums [1,1,1,1,1,1,1,1]
输出0提示
1 target 1091 nums.length 1051 nums[i] 105 进阶
如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。 解题思路
From代码随想录
滑动窗口
接下来就开始介绍数组操作中另一个重要的方法滑动窗口。
所谓滑动窗口就是不断的调节子序列的起始位置和终止位置从而得出我们要想的结果。
在暴力解法中是一个for循环滑动窗口的起始位置一个for循环为滑动窗口的终止位置用两个for循环 完成了一个不断搜索区间的过程。
那么滑动窗口如何用一个for循环来完成这个操作呢。
首先要思考 如果用一个for循环那么应该表示 滑动窗口的起始位置还是终止位置。
如果只用一个for循环来表示 滑动窗口的起始位置那么如何遍历剩下的终止位置
此时难免再次陷入 暴力解法的怪圈。
所以 只用一个for循环那么这个循环的索引一定是表示 滑动窗口的终止位置。
那么问题来了 滑动窗口的起始位置如何移动呢
这里还是以题目中的示例来举例s7 数组是 231243来看一下查找的过程 最后找到 43 是最短距离。
其实从动画中可以发现滑动窗口也可以理解为双指针法的一种只不过这种解法更像是一个窗口的移动所以叫做滑动窗口更适合一些。
在本题中实现滑动窗口主要确定如下三点
窗口内是什么如何移动窗口的起始位置如何移动窗口的结束位置
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
窗口的起始位置如何移动如果当前窗口的值大于s了窗口就要向前移动了也就是该缩小了。
窗口的结束位置如何移动窗口的结束位置就是遍历数组的指针也就是for循环里的索引。
解题的关键在于 窗口的起始位置如何移动如图所示 可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。 代码如下 Java写代码还是不太习惯什么时候加空格什么时候换行。。
class Solution {public int minSubArrayLen(int target, int[] nums) {int left 0;int sum 0;int result Integer.MAX_VALUE;for (int right 0; right nums.length; right) {sum nums[right];while(sum target) {if(result (right - left 1)) result right - left 1;sum - nums[left];}}if (result Integer.MAX_VALUE) return 0;else return result;}
}
