本篇文章中会带大家从零基础到学会利用滑动窗口的思想解决算法题,我从力扣上筛选了三道题,难度由浅到深,会附上题目链接以及算法原理和解题代码,希望大家能坚持看完,绝对能有收获,大家有更好的思路也欢迎大家在评论区交流啊! 欢迎大家交流!!! 欢迎大家交流!!! 欢迎大家交流!!!
文章顺序:
题目链接-》算法原理-》代码呈现
思想总结:
滑动窗口可以理解为是快慢双指针的一个分支,也是利用双指针一个在前一个在后,通过判断条件使两个指针形成一个大小不断变化的窗口,不断向前移动。滑动窗口的解题思想是在暴力枚举的思想上演化而来的,利用数据的单调性使快指针不用回退,通常能使算法复杂度在暴力枚举的基础上减少一个数量级。
题目链接:
https://leetcode.cn/problems/minimum-size-subarray-sum/description/
算法思想:
由于此问题分析的对象是「⼀段连续的区间」,因此可以考虑「滑动窗⼝」的思想来解决这道题。
让滑动窗⼝满⾜:从 i 位置开始,窗⼝内所有元素的和⼩于 target (那么当窗⼝内元素之和
第⼀次⼤于等于⽬标值的时候,就是 i 位置开始,满⾜条件的最⼩⻓度)。
做法:将右端元素划⼊窗⼝中,统计出此时窗⼝内元素的和:
为什么使用滑动窗口?
这个窗⼝寻找的是:以当前窗⼝最左侧元素(记为 left1 )为基准,符合条件的情况。也
就是在这道题中,从 left1 开始,满⾜区间和 sum >= target 时的最右侧(记为
right1 )能到哪⾥。
时间复杂度:虽然代码是两层循环,但是我们的 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;
}
}
题目链接:
https://leetcode.cn/problems/fruit-into-baskets/description/
算法思路:
研究的对象是⼀段连续的区间,可以使⽤「滑动窗⼝」思想来解决问题。
让滑动窗⼝满⾜:窗⼝内⽔果的种类只有两种。
做法:右端⽔果进⼊窗⼝的时候,⽤哈希表统计这个⽔果的频次。这个⽔果进来后,判断哈希表的
大小:
算法流程:
代码呈现:
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;
}
}
题目链接:
算法思路:
代码呈现:
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;
}
}