跟着代码随想录 三 滑动窗口解决长度最小的子数组
哈喽哈喽,我是你们的金樽清酒,今天我分享的是如何用滑动窗口来解决长度最小的子数组的问题。我在看代码随想的时候,想了一下这个问题。我为什么要跟着代码随想录。因为盲目的刷leetcode问题得不到分类总结,可能做出来一题也只能暴力求解,性能不是很好。最近在看数组篇章,优化数组用的最多的就是双指针了,今天也是用双指针来解决问题,不过这个双指针更类似一个窗口,我们叫它滑动窗口。
先看一下leet题
给定一个含有 n
****个正整数的数组和一个正整数 target
。
找出该数组中满足其和 ****≥ target
****的长度最小的 连续子数组 [numsl, numsl+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 <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
看到这道题,我们可能会用暴力求解的办法来做,但是显然性能不是很好。
如何实现滑动窗口
主要确定以下三点
- 窗口的元素是什么?
- 如何移动窗口的起始位置?
- 如何移动窗口的终止位置?
就这么看可能看不懂,上代码。
代码
let nums = [4, 6, 2, 4, 9, 8, 7]
let mimsubArrayLen = (arr, s) => {//此函数的功能就是找到加起来值为s的最小子数组的长度,用滑动窗口,双指针的方法来写
let result = Number.MAX_VALUE;//给result初始值赋值为无穷大
let sum = 0;//滑动窗口的数值之和
let i = 0;//滑动窗口的起始位置
let subLen = 0;//滑动窗口的长度
for (let j = 0; j < arr.length; j++) {
sum += arr[j]
while (sum >= s) {
subLen = (j - i + 1)//获取子数组的长度
result = result < subLen ? result : subLen;
sum -= arr[i++]//这个就是滑动窗口的精髓,调整初始指针的位置
}
}
//如果result没有被赋值则说明没有符合条件的子数组,也就是没有被赋值,返回0
//如何判断result没有被赋值过呢???
return result == Number.MAX_VALUE ? 0 : result;
}//这个是匿名箭头函数
console.log(mimsubArrayLen(nums, 12));//
sum -= arr[i++]//这个就是滑动窗口的精髓,调整初始指针的位置。但已经满足条件之后,我们将初始指针后移,元素值减掉,后面的指针依旧往后,就可以像移动一个窗口一样。
let result = Number.MAX_VALUE;//给result初始值赋值为无穷大,如果子数组的长度小于它就得子数组长度赋值给result。不然一直是无穷大,也就是说没有符合条件的子数组,这样这道题就完成啦。
小伙伴们如果有更好的刷题方式可以告诉小编一下哦,小编现在多多少少有点小菜。
原文链接:https://juejin.cn/post/7357716989782065179 作者:jinzunqinjiu