北京网站建设制作案例,悟空crm官网,国内外优秀室内设计案例,企业网站建设代理公司版本说明
当前版本号[20230808]。
版本修改说明20230808初版
目录 文章目录 版本说明目录209.长度最小的子数组思路暴力解法滑动窗口 两种方法的区别总结 209.长度最小的子数组
力扣题目链接 更多内容可点击此处跳转到代码随想录#xff0c;看原版文件
给定一个含有 n 个…版本说明
当前版本号[20230808]。
版本修改说明20230808初版
目录 文章目录 版本说明目录209.长度最小的子数组思路暴力解法滑动窗口 两种方法的区别总结 209.长度最小的子数组
力扣题目链接 更多内容可点击此处跳转到代码随想录看原版文件
给定一个含有 n 个正整数的数组和一个正整数 s 找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组并返回其长度。如果不存在符合条件的子数组返回 0。
示例
输入s 7, nums [2,3,1,2,4,3]输出2解释子数组 [4,3] 是该条件下的长度最小的子数组。
提示
1 target 10^91 nums.length 10^51 nums[i] 10^5 思路
暴力解法
这道题目暴力解法当然是 两个for循环然后不断的寻找符合条件的子序列时间复杂度很明显是O(n^2)。
代码如下
class Solution {/*** 使用滑动窗口方法来找到最小长度的子数组*s 目标值* nums正整数数组* 最小长度的子数组的长度*/public int minSubArrayLen(int s, int[] nums) {int result Integer.MAX_VALUE; // 最终的结果默认为最大值int sum 0; // 子序列的数值之和int subLength 0; // 子序列的长度for (int i 0; i nums.length; i) { // 设置子序列起点为isum 0;for (int j i; j nums.length; j) { // 设置子序列终止位置为jsum nums[j];if (sum s) { // 一旦发现子序列和超过了s更新resultsubLength j - i 1; // 取子序列的长度result Math.min(result, subLength); // 更新result为较小值break; // 因为我们是找符合条件最短的子序列所以一旦符合条件就break}}}// 如果result没有被赋值的话就返回0说明没有符合条件的子序列return result Integer.MAX_VALUE ? 0 : result;}
}时间复杂度O(n^2)空间复杂度O(1)
后面力扣更新了数据暴力解法已经超时了。
滑动窗口
接下来就开始介绍数组操作中另一个重要的方法滑动窗口。
所谓滑动窗口就是不断的调节子序列的起始位置和终止位置从而得出我们要想的结果。
在暴力解法中是一个for循环滑动窗口的起始位置一个for循环为滑动窗口的终止位置用两个for循环 完成了一个不断搜索区间的过程。
那么滑动窗口如何用一个for循环来完成这个操作呢
首先要思考 如果用一个for循环那么应该表示 滑动窗口的起始位置还是终止位置。
如果只用一个for循环来表示 滑动窗口的起始位置那么如何遍历剩下的终止位置
此时难免再次陷入 暴力解法的怪圈。
所以 只用一个for循环那么这个循环的索引一定是表示 滑动窗口的终止位置。
那么问题来了 滑动窗口的起始位置如何移动呢
这里还是以题目中的示例来举例s7 数组是 231243来看一下查找的过程
第一步设ij为滑动窗口开始、终止位置 第二步i开始向右走直到走到累加的和大于等于7停下来
2 3 5 7 2 3 1 6 7 2 3 1 2 8 7 长度为4 第三步当出现i累加的和大于等于7并且已经停下来后终止位置j开始向右移动当走到滑动窗口不再大于等于7就停下来 第四步此时滑动窗口已不再大于等于7了i就可以继续向右走了 第五步此时滑动窗口已经大于等于7了j就向右移到滑动窗口不大于等于7的位置就可以了会发现1 2 4 7需要继续向右走 长度为3 2 4 7j停止走动 第六步滑动窗口不再大于等于7了i继续向右走 第七步滑动窗口已大于等于7了2 4 3 9 7 长度为3 , j继续向下移动 最后找到 43 长度为2 是最短距离。
其实从动画中可以发现**滑动窗口也可以理解为双指针法的一种**只不过这种解法更像是一个窗口的移动所以叫做滑动窗口更适合一些。
在本题中实现滑动窗口主要确定如下三点
窗口内是什么如何移动窗口的起始位置如何移动窗口的结束位置
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
窗口的起始位置如何移动如果当前窗口的值大于s了窗口就要向前移动了也就是该缩小了。
窗口的结束位置如何移动窗口的结束位置就是遍历数组的指针也就是for循环里的索引。
解题的关键在于 窗口的起始位置如何移动如图所示 可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。
代码如下
class Solution {/*** 使用滑动窗口方法来找到最小长度的子数组* s 目标值*nums 正整数数组*return 最小长度的子数组的长度*/public int minSubArrayLen(int s, 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 s) { // 当滑动窗口的和大于等于目标值result Math.min(result, right - left 1); // 更新最小长度sum - nums[left]; // 左指针右移从滑动窗口的和中减去左边界的元素}}return result Integer.MAX_VALUE ? 0 : result; // 返回最小长度如果不存在满足条件的子数组则返回0}
}时间复杂度O(n)空间复杂度O(1)
一些录友会疑惑为什么时间复杂度是O(n)。
不要以为for里放一个while就以为是O(n^2)啊 主要是看每一个元素被操作的次数每个元素在滑动窗后进来操作一次出去操作一次每个元素都是被操作两次所以时间复杂度是 2 × n 也就是O(n)。
两种方法的区别
暴力解法和滑动窗口方法之间的区别如下
暴力解法 暴力解法是一种简单直接的方法在给定数组中遍历所有可能的连续子数组计算它们的和然后找到满足和大于等于目标值s的最小长度。具体操作是使用两个嵌套的for循环外层循环遍历所有可能的起始位置内层循环遍历以当前起始位置为起点的所有连续子数组。对于每个子数组计算它们的和并与目标值s进行比较。如果和大于等于目标值s则更新最小长度。这种方法的时间复杂度为O(n^2)因为需要遍历所有可能的子数组。在最坏的情况下数组中可能会有n个连续子数组。空间复杂度为O(1)因为只使用了常数级别的额外空间。 滑动窗口方法 滑动窗口方法使用两个指针来构建滑动窗口左指针和右指针分别表示滑动窗口的左边界和右边界。首先将左指针和右指针都指向数组的第一个元素。然后移动右指针将元素逐个加到滑动窗口的和中直到滑动窗口的和大于等于目标值s为止。当滑动窗口的和大于等于目标值s时记录当前滑动窗口的长度并更新最小长度。然后移动左指针将滑动窗口的左边界向右移动一位并从滑动窗口的和中减去左边界的元素。重复上述步骤直到右指针达到数组的末尾。这种方法的时间复杂度为O(n)因为每个元素最多被访问两次左指针和右指针没有遍历所有可能的子数组。空间复杂度为O(1)除了常数级别的几个变量外没有使用额外的空间。
对于给定的示例输入s 7, nums [2,3,1,2,4,3]滑动窗口方法可以在O(n)的时间复杂度内找到满足条件的最小长度子数组而暴力解法则需要O(n^2)的时间复杂度。因此滑动窗口方法更高效。
总结
使用滑动窗口方法可以解决这个问题。定义两个指针分别表示滑动窗口的左右边界。初始化左指针和右指针都指向数组的第一个元素。然后移动右指针将元素逐个加到滑动窗口的和中直到滑动窗口的和大于等于目标值s为止。当滑动窗口的和大于等于目标值s时记录当前滑动窗口的长度并更新最小长度。然后移动左指针将滑动窗口的左边界向右移动一位并从滑动窗口的和中减去左边界的元素。重复步骤3到步骤5直到右指针达到数组的末尾。返回最小长度如果不存在满足条件的子数组则返回0。
时间复杂度分析使用滑动窗口每个元素最多会被访问两次左指针和右指针所以时间复杂度为O(n)。空间复杂度分析空间复杂度为O(1)。除了常数级别的几个变量外没有使用额外的空间。
调用minSubArrayLen方法进行测试。将给定的数组nums和目标值s传递给方法并将返回结果打印出来。预期输出为2这是因为数组中的子数组[4, 3]的元素之和为7且为满足条件的最小长度子数组。
测试代码
package shuzhu;public class Day04 {public static int minSubArrayLen(int[] nums, int s) {int left 0;int sum 0;int result Integer.MAX_VALUE;for(int right 0;right nums.length;right){sum nums[right];while(sum s){result Math.min(result, right-left1);sum - nums[left];}}return result Integer.MAX_VALUE ? 0 : result;}public static void main(String[] args) {int[] nums {2, 3, 1, 2, 4, 3};int s 7;int result minSubArrayLen(nums, s);System.out.println(长度最小的连续数组其长度为result);}
}return result Integer.MAX_VALUE ? 0 : result;}public static void main(String[] args) {int[] nums {2, 3, 1, 2, 4, 3};int s 7;int result minSubArrayLen(nums, s);System.out.println(长度最小的连续数组其长度为result);}
}
