东莞百度网站推广,wordpress 空间商,app平台运营模式,网站做视频怎么赚钱的滑动窗口 本篇文章中会带大家从零基础到学会利用滑动窗口的思想解决算法题#xff0c;我从力扣上筛选了三道题#xff0c;难度由浅到深#xff0c;会附上题目链接以及算法原理和解题代码#xff0c;希望大家能坚持看完#xff0c;绝对能有收获#xff0c;大家有更好的思…滑动窗口 本篇文章中会带大家从零基础到学会利用滑动窗口的思想解决算法题我从力扣上筛选了三道题难度由浅到深会附上题目链接以及算法原理和解题代码希望大家能坚持看完绝对能有收获大家有更好的思路也欢迎大家在评论区交流啊 欢迎大家交流 欢迎大家交流 欢迎大家交流 文章顺序
题目链接-》算法原理-》代码呈现
思想总结 滑动窗口可以理解为是快慢双指针的一个分支也是利用双指针一个在前一个在后通过判断条件使两个指针形成一个大小不断变化的窗口不断向前移动。滑动窗口的解题思想是在暴力枚举的思想上演化而来的利用数据的单调性使快指针不用回退通常能使算法复杂度在暴力枚举的基础上减少一个数量级。 1.长度最小的子数组
题目链接
https://leetcode.cn/problems/minimum-size-subarray-sum/description/
算法思想 由于此问题分析的对象是「⼀段连续的区间」因此可以考虑「滑动窗⼝」的思想来解决这道题。 让滑动窗⼝满⾜从 i 位置开始窗⼝内所有元素的和⼩于 target 那么当窗⼝内元素之和 第⼀次⼤于等于⽬标值的时候就是 i 位置开始满⾜条件的最⼩⻓度。 做法将右端元素划⼊窗⼝中统计出此时窗⼝内元素的和 如果窗⼝内元素之和⼤于等于 target 更新结果并且将左端元素划出去的同时继续判断是否满⾜条件并更新结果因为左端元素可能很⼩划出去之后依旧满⾜条件 如果窗⼝内元素之和不满⾜条件 right 另下⼀个元素进⼊窗⼝ 为什么使用滑动窗口 这个窗⼝寻找的是以当前窗⼝最左侧元素记为 left1 为基准符合条件的情况。也 就是在这道题中从 left1 开始满⾜区间和 sum target 时的最右侧记为 right1 能到哪⾥。 我们既然已经找到从 left1 开始的最优的区间那么就可以⼤胆舍去 left1 。但是如果继续像⽅法⼀⼀样重新开始统计第⼆个元素 left2 往后的和势必会有⼤量重复的计算因为我们在求第⼀段区间的时候已经算出很多元素的和了这些和是可以在计算下次区间和的时候⽤上的。 此时 rigth1 的作⽤就体现出来了我们只需将 left1 这个值从 sum 中剔除。从right1 这个元素开始往后找满⾜ left2 元素的区间此时 right1 也有可能是满⾜的因为 left1 可能很⼩。 sum 剔除掉 left1 之后依旧满⾜⼤于等于 target 。这样我们就能省掉⼤量重复的计算。 这样我们不仅能解决问题⽽且效率也会⼤⼤提升。 时间复杂度虽然代码是两层循环但是我们的 left 指针和 right 指针都是不回退的两者 最多都往后移动 n 次。因此时间复杂度是 O(N)。 代码呈现
class Solution {public int minSubArrayLen(int target, int[] nums) {int left0;int right0;int nnums.length;int sum0;int min0;for(int i0;in;i){sumnums[right];right;while(true){if(sumtarget){int aright-left;if(mina||min0){mina;}sum-nums[left];left;}else{break;}}}return min;}
}
2. 水果成篮 题目链接
https://leetcode.cn/problems/fruit-into-baskets/description/ 算法思路 研究的对象是⼀段连续的区间可以使⽤「滑动窗⼝」思想来解决问题。 让滑动窗⼝满⾜窗⼝内⽔果的种类只有两种。 做法右端⽔果进⼊窗⼝的时候⽤哈希表统计这个⽔果的频次。这个⽔果进来后判断哈希表的 大小 如果⼤⼩超过 2说明窗⼝内⽔果种类超过了两种。那么就从左侧开始依次将⽔果划出窗⼝直到哈希表的大小小于等于 2然后更新结果 如果没有超过 2说明当前窗⼝内⽔果的种类不超过两种直接更新结果 ret。
算法流程
初始化哈希表 hash 来统计窗⼝内⽔果的种类和数量 初始化变量左右指针 left 0right 0记录结果的变量 ret 0 当 right ⼩于数组⼤⼩的时候⼀直执⾏下列循环 1. 将当前⽔果放⼊哈希表中 2. 判断当前⽔果进来后哈希表的⼤⼩ 如果超过 2 -将左侧元素滑出窗⼝并且在哈希表中将该元素的频次减⼀ -如果这个元素的频次减⼀之后变成了 0就把该元素从哈希表中删除 -重复上述两个过程直到哈希表中的⼤⼩不超过 2 3. 更新结果 ret 4. right让下⼀个元素进⼊窗⼝ 循环结束后ret 存的就是最终结果
代码呈现
class Solution {public int totalFruit(int[] f) {MapInteger,Integer hashnew HashMap();int ret0;for(int left0,right0;rightf.length;right){int inf[right];hash.put(in,hash.getOrDefault(in,0)1);while(hash.size()2){int outf[left];hash.put(out,hash.get(out)-1);if(hash.get(out)0){hash.remove(out);}left;}retMath.max(ret,right-left1);}return ret;}
} 3.找到字符串中所以字母异位词
题目链接
找到字符串中所有字母异位词 算法思路
因为字符串 p 的异位词的⻓度⼀定与字符串 p 的⻓度相同所以我们可以在字符串 s 中构造⼀个⻓度为与字符串 p 的⻓度相同的滑动窗⼝并在滑动中维护窗⼝中每种字⺟的数量 当窗⼝中每种字⺟的数量与字符串 p 中每种字⺟的数量相同时则说明当前窗⼝为字符串 p的异位词 因此可以⽤两个⼤⼩为 26 的数组来模拟哈希表⼀个来保存 s 中的⼦串每个字符出现的个数另⼀个来保存 p 中每⼀个字符出现的个数。这样就能判断两个串是否是异位词。
代码呈现
class Solution {public ListInteger findAnagrams(String s, String p) {char[] arr1 s.toCharArray();int n arr1.length;char[] arr2 p.toCharArray();ListInteger list new ArrayList();MapCharacter, Integer hash new HashMap();for (int i 0; i arr2.length; i) {hash.put(arr2[i], hash.getOrDefault(arr2[i], 0) 1);}if (hash.isEmpty()) {return list;}MapCharacter, Integer hash1 new HashMap();for (int left 0, right 0; right n; right) { if (hash.containsKey(arr1[right])) {hash1.put(arr1[right], hash1.getOrDefault(arr1[right], 0) 1);while(hash1.get(arr1[right])hash.get(arr1[right])){hash1.put(arr1[left],hash1.get(arr1[left])-1);left;}} else {leftright1;hash1.clear();}if (hash.equals(hash1)) {list.add(left);hash1.put(arr1[left],hash1.get(arr1[left])-1);left;}}return list;}
}
