【算法题】三道题理解算法思想--滑动窗口篇
【算法题】三道题理解算法思想--滑动窗口篇
滑动窗口
本篇文章中会带大家从零基础到学会利用滑动窗口的思想解决算法题，我从力扣上筛选了三道题，难度由浅到深，会附上题目链接以及算法原理和解题代码，希望大家能坚持看完，绝对能有收获，大家有更好的思路也欢迎大家在评论区交流啊！ 欢迎大家交流！！！ 欢迎大家交流！！！ 欢迎大家交流！！！
文章顺序：
题目链接-》算法原理-》代码呈现
思想总结：
滑动窗口可以理解为是快慢双指针的一个分支，也是利用双指针一个在前一个在后，通过判断条件使两个指针形成一个大小不断变化的窗口，不断向前移动。滑动窗口的解题思想是在暴力枚举的思想上演化而来的，利用数据的单调性使快指针不用回退，通常能使算法复杂度在暴力枚举的基础上减少一个数量级。
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 left=0;
int right=0;
int n=nums.length;
int sum=0;
int min=0;
for(int i=0;i<n;i++){
sum+=nums[right];
right++;
while(true){
if(sum>=target){
int a=right-left;
if(min>a||min==0){
min=a;
}
sum-=nums[left];
left++;
}else{
break;
}
}
}
return min;
}
}2. 水果成篮
题目链接：
https://leetcode.cn/problems/fruit-into-baskets/description/
算法思路：
研究的对象是⼀段连续的区间，可以使⽤「滑动窗⼝」思想来解决问题。
让滑动窗⼝满⾜：窗⼝内⽔果的种类只有两种。
做法：右端⽔果进⼊窗⼝的时候，⽤哈希表统计这个⽔果的频次。这个⽔果进来后，判断哈希表的
大小：
- 如果⼤⼩超过 2：说明窗⼝内⽔果种类超过了两种。那么就从左侧开始依次将⽔果划出窗⼝，直到哈希表的大小小于等于 2，然后更新结果；
- 如果没有超过 2，说明当前窗⼝内⽔果的种类不超过两种，直接更新结果 ret。
算法流程：
- 初始化哈希表 hash 来统计窗⼝内⽔果的种类和数量；
- 初始化变量：左右指针 left = 0，right = 0，记录结果的变量 ret = 0；
- 当 right ⼩于数组⼤⼩的时候，⼀直执⾏下列循环： 1. 将当前⽔果放⼊哈希表中； 2. 判断当前⽔果进来后，哈希表的⼤⼩： 如果超过 2： -将左侧元素滑出窗⼝，并且在哈希表中将该元素的频次减⼀； -如果这个元素的频次减⼀之后变成了 0，就把该元素从哈希表中删除； -重复上述两个过程，直到哈希表中的⼤⼩不超过 2； 3. 更新结果 ret； 4. right++，让下⼀个元素进⼊窗⼝
- 循环结束后，ret 存的就是最终结果
代码呈现：
class Solution {
public int totalFruit(int[] f) {
Map<Integer,Integer> hash=new HashMap<>();
int ret=0;
for(int left=0,right=0;right<f.length;right++){
int in=f[right];
hash.put(in,hash.getOrDefault(in,0)+1);
while(hash.size()>2){
int out=f[left];
hash.put(out,hash.get(out)-1);
if(hash.get(out)==0){
hash.remove(out);
}
left++;
}
ret=Math.max(ret,right-left+1);
}
return ret;
}
}3.找到字符串中所以字母异位词
题目链接：
算法思路：
- 因为字符串 p 的异位词的⻓度⼀定与字符串 p 的⻓度相同，所以我们可以在字符串 s 中构造⼀个⻓度为与字符串 p 的⻓度相同的滑动窗⼝，并在滑动中维护窗⼝中每种字⺟的数量；
- 当窗⼝中每种字⺟的数量与字符串 p 中每种字⺟的数量相同时，则说明当前窗⼝为字符串 p的异位词；
- 因此可以⽤两个⼤⼩为 26 的数组来模拟哈希表，⼀个来保存 s 中的⼦串每个字符出现的个数，另⼀个来保存 p 中每⼀个字符出现的个数。这样就能判断两个串是否是异位词。
代码呈现：
class Solution {
public List<Integer> findAnagrams(String s, String p) {
char[] arr1 = s.toCharArray();
int n = arr1.length;
char[] arr2 = p.toCharArray();
List<Integer> list = new ArrayList<>();
Map<Character, 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;
}
Map<Character, 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 {
left=right+1;
hash1.clear();
}
if (hash.equals(hash1)) {
list.add(left);
hash1.put(arr1[left],hash1.get(arr1[left])-1);
left++;
}
}
return list;
}
}