滑动窗口算法的本质是双指针法中的左右指针法,所谓滑动窗口,就像描述的那样,可以理解成是一个会滑动的窗口,每次记录下窗口的状态,再找出符合条件的适合的窗口。它可以将双层嵌套的循环问题,转换为单层遍历的循环问题。使用两个指针一左一右构成一个窗口,就可以将二维循环的问题转化成一维循环一次遍历,相当于通过旧有的计算结果对搜索空间进行剪枝,使时间复杂度从O(n²)降低至O(n),比如经典字符串查找算法Rabin-Karp 指纹字符串查找算法,它本质上也使用了滑动窗口的思想,通过公式推导降低窗口滑动时计算子串哈希值的复杂度。
滑动窗口算法更多的是一种思想或技巧,按照窗口大小是否固定分为固定滑动窗口和变长滑动窗口,可以用来解决一些查找满足一定条件的连续区间的性质(长度等)的问题。往往类似于“请找到满足xx的最x的区间(子串、子数组等)的xx”这类问题都可以使用该方法进行解决。
以下思路是比较形象的滑动窗口问题的解题步骤,但有些题目找到窗口限定比较隐晦,需要具体问题具体分析:
(1)初始化窗口:
初始化左右边界 left = right = 0,把索引闭区间 [left, right] 称为一个「窗口」。
(2)寻找可行解:
我们先不断地增加 right 指针扩大窗口 [left, right],直到窗口中的满足可行解。
(3)优化可行解:
此时,我们停止增加 right,转而不断增加 left 指针缩小窗口 [left, right],直到窗口中的可行解不再符合要求。同时,每次增加 left,我们都要更新一轮结果。
(4)滑动窗口,直至一次遍历结束:
重复第 2 和第 3 步,直到 right 到达到的尽头。
这个思路其实也不难理解,第 2 步相当于在寻找一个「可行解」,然后第 3 步在优化这个「可行解」,最终找到最优解。左右指针轮流前进,窗口大小增增减减,窗口不断向右滑动。
public void slideWindowTemplate(String nums){ int l = 0, r = 0; //[初始化窗口] //codes... [其他初始化信息,定义一些维护数据的数据结构] while(r < nums.length){ //codes..... [维护窗口中的数据] while(l < r && check(xxx) == false){ //[窗口不满足某种性质] //codes... [维护窗口中的数据] l++; //[缩小窗口] } //codes.. [更新结果] r++; //[增大窗口] } }
public void slideWindowTemplate(String nums){ //codes... [其他初始化信息,定义一些维护数据的数据结构] for(int l = 0, r = 0; r < nums.length; r++){ //codes..... [维护窗口中的数据] while(l < r && check(xxx) == false){ //[窗口不满足某种性质] //codes... [维护窗口中的数据] l++; //[缩小窗口] } //codes.. [更新结果] } }
模板1和模板2算法本质是一样的,只是实现不同,读者可根据爱好来选择。
例题分为三种级别,一是入门级题目,二是进阶题目,三是经典题目分别挑选一道题进行讲解。
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [ n u m s l , n u m s l + 1 , . . . , n u m s r − 1 , n u m s r ] [nums_l, nums_{l+1}, ..., nums_{r-1}, nums_r] [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
本题为变长的滑动窗口,其窗口大小由target决定(窗口总和大于等于target),所以定义一个变量(窗口内总和),小于target右指针右移,大于target左指针右移,等于记录更新窗口大小即可
package com.algorithm.num209; /** * 思路:滑动窗口实现,定义一个变量(窗口内总和), * 小于target右指针右移,大于target左指针右移,等于记录更新窗口大小 * * @author hh * @date 2022-2-3 20:10 */ public class Solution { public int minSubArrayLen(int target, int[] nums) { int result = Integer.MAX_VALUE; int numsLen = nums.length; int winNums = 0; //双指针l,r for(int l = 0,r = 0; r < numsLen; r++){ winNums += nums[r]; //如果区间和大于target左指针右移 while (winNums >= target){ //先更新长度 result = Math.min(result,r - l + 1); //缩小左窗口 winNums -= nums[l]; l++; } } return result == Integer.MAX_VALUE ? 0 : result; } }
给你一个整数数组 nums 和一个整数 k ,判断数组中是否存在两个 不同的索引 i 和 j ,满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在,返回 true ;否则,返回 false 。
示例 1:
输入:nums = [1,2,3,1], k = 3
输出:true
示例 2:输入:nums = [1,0,1,1], k = 1
输出:true
示例 3:输入:nums = [1,2,3,1,2,3], k = 2
输出:false
滑动窗口,窗口最大为k,其中r - l <= k,把窗口中的元素保存到集合中,每次左右指针移动更新集合即可,如果集合中存在元素则返回true
package com.algorithm.num219; import java.util.LinkedHashSet; import java.util.Set; /** * 思路:滑动窗口,窗口最大为k,其中r - l <= k,把窗口中的元素保存到集合中,每次 * 左右指针移动更新集合即可,如果集合中存在元素则返回true * * @author hh * @date 2022-2-3 21:18 */ public class Solution { public boolean containsNearbyDuplicate(int[] nums, int k) { int numLength = nums.length; Set<Integer> set = new LinkedHashSet<>(); for(int l = 0, r = 0; r < numLength; r++){ //判断集合中是否存在,存在则直接返回true,没有则添加到集合中 if(set.contains(nums[r])){ return true; } set.add(nums[r]); //如果窗口大小则缩小窗口 while (r - l >= k){ set.remove(nums[l]); l++; } } return false; } }
给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j,使得 abs(nums[i] - nums[j]) <= t ,同时又满足 abs(i - j) <= k 。
如果存在则返回 true,不存在返回 false。
示例 1:
输入:nums = [1,2,3,1], k = 3, t = 0
输出:true
示例 2:输入:nums = [1,0,1,1], k = 1, t = 2
输出:true
示例 3:输入:nums = [1,5,9,1,5,9], k = 2, t = 3
输出:false
地址: 220. 存在重复元素 III
本题与219题目非常类型,只不过条件有了变化。所以可以选取数据结构TreeSet来实现。使用TreeSet保存窗口中元素,窗口扩大时需要判断有没有大于等于nums[r] - t的元素,如果有,则返回为true,当达到窗口大小缩小窗口,并移除窗口中的元素即可
package com.algorithm.num220; import java.util.TreeSet; /** * 思路:滑动窗口,使用TreeSet保存窗口中元素,窗口扩大时需要判断有没有大于等于nums[r] - t的元素, * 如果有,则返回为true,当达到窗口大小缩小窗口,并移除窗口中的元素即可 * * @author hh * @date 2022-2-3 21:44 */ public class Solution { public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { int numsLength = nums.length; TreeSet<Long> treeSet = new TreeSet<>(); for(int l = 0,r = 0; r < numsLength; r++){ long down = (long) nums[r] - t; long up = (long)nums[r] + t; //同时满足上下限 Long cellingVal = treeSet.ceiling(down); Long floorVal = treeSet.floor(up); if((cellingVal != null && cellingVal <= nums[r]) || (floorVal != null && floorVal >= nums[r])){ return true; } treeSet.add((long)nums[r]); //是否到达窗口的最大 while (r - l >= k){ treeSet.remove((long)nums[l]); l++; } } return false; } }
给你一个字符串 s
和一个整数 k
,请你找出 s
中的最长子串, 要求该子串中的每一字符出现次数都不少于 k
。返回这一子串的长度。
示例 1:
输入:s = “aaabb”, k = 3
输出:3
解释:最长子串为 “aaa” ,其中 'a’ 重复了 3 次。
示例 2:输入:s = “ababbc”, k = 2
输出:5
解释:最长子串为 “ababb” ,其中 'a’ 重复了 2 次, 'b’ 重复了 3 次。
题目说明了只包含小写字母(26 个,为有限数据),我们可以枚举最大长度所包含的字符类型数量,答案必然是 [1, 26],即最少包含 1 个字母,最多包含 26 个字母。
你会发现,当确定了长度所包含的字符种类数量时,区间重新具有了二段性质。
当我们使用双指针的时候:
右端点往右移动必然会导致字符类型数量增加(或不变)
左端点往右移动必然会导致字符类型数量减少(或不变)
当然,我们还需要记录有多少字符符合要求(出现次数不少于 k),当区间内所有字符都符合时更新答案。
package com.algorithm.num395; /** * 思路:滑动窗口,但本题关键是无法确定窗口的大小,由于字母仅限小写英文字母,所以我们可以枚举窗口中字母类型数量, * 从1到26,这样就限定了窗口的大小,从而解决问题。定义一个变量winCharTypeNums保存当前窗口的字母类型数量,当枚举 * 字母类型数量大于winCharTypeNums时扩大窗口,等于时更新最大长度,小于时缩小窗口。保存字母数量使用数组保存, * 扩大或缩小时更新数组 * * @author hh * @date 2022-2-4 11:16 */ public class Solution { /** * 记录满足条件的最大长度 */ private int maxLength = Integer.MIN_VALUE; public int longestSubstring(String s, int k) { int strLength = s.length(); for(int enumNum = 1; enumNum <= 26; enumNum ++){ //定义变量 int winCharTypeNums = 0; int[] frequency = new int[26]; for(int l = 0,r = 0; r < strLength; r++){ //判断之前数组是否记录,没有记录则winCharTypeNums加1,否则只更新数组 int rightCharIndex = s.charAt(r) - 'a'; if(frequency[rightCharIndex] == 0){ winCharTypeNums++; } frequency[rightCharIndex] ++; //检查更新满足条件的最大长度 if(winCharTypeNums == enumNum){ check(frequency,k); } //检测是否需要缩小窗口 while (winCharTypeNums > enumNum){ //获取左边界字符,判断是否需要更新winCharTypeNums int leftCharIndex = s.charAt(l) - 'a'; if(frequency[leftCharIndex] == 1){ winCharTypeNums--; } frequency[leftCharIndex]--; l++; } } } return maxLength == Integer.MIN_VALUE ? 0 : maxLength; } private void check(int[] frequency,int k){ int strLength = 0; for (int value : frequency) { if (value != 0 && value < k) { return; } strLength += value; } maxLength = Math.max(strLength,maxLength); } }
给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。
示例 1:
输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。
示例 2:输入: s = “abab”, p = “ab”
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。
根据题目要求,我们需要在字符串 s 寻找字符串 p的异位词。因为字符串 p 的异位词的长度一定与字符串 p 的长度相同,所以我们可以在字符串 s 中构造一个长度为与字符串 p 的长度相同的滑动窗口,并在滑动中维护窗口中每种字母的数量;当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时,则说明当前窗口为字符串 p 的异位词
package com.algorithm.num438; import java.util.LinkedList; import java.util.List; /** * 思路:滑动窗口,窗口大小固定,每次滑动时需比较是否为异位词 * * @author hh * @date 2022-2-4 17:39 */ public class Solution { public List<Integer> findAnagrams(String s, String p) { List<Integer> result = new LinkedList<>(); int[] pat = new int[26]; int[] text = new int[26]; int strLength = s.length(); for(char c : p.toCharArray()){ pat[c - 'a']++; } for(int l = 0,r = 0; r < strLength; r++){ text[s.charAt(r) - 'a'] ++; if(l + p.length() - 1 == r && this.isAnagrams(text,pat)){ //检测是否为异位词 result.add(l); } while (l + p.length() - 1 <= r){ text[s.charAt(l) - 'a']--; l++; } } return result; } private boolean isAnagrams(int[] text,int[] pat){ for(int i = 0; i < text.length; i++){ if(text[i] != pat[i]){ return false; } } return true; } }
在方法一的基础上,我们不再分别统计滑动窗口和字符串 p 中每种字母的数量,而是统计滑动窗口和字符串 p中每种类型字母的差;并引入变量differ 来记录当前窗口与字符串 p 中数量不同类型的字母的,并在滑动窗口的过程中维护它。
在判断滑动窗口中每种字母的数量与字符串 p 中每种字母的数量是否相同时,只需要判断 differ 是否为零即可。
package com.algorithm.num438; import java.util.LinkedList; import java.util.List; /** * @author hh * @date 2022-2-4 21:20 */ public class Solution2 { public List<Integer> findAnagrams(String s, String p) { List<Integer> result = new LinkedList<>(); if(s.length() < p.length()){ return result; } //维护窗口的差值 int[] diffArr = new int[26]; //diff表示字符类型不同的数量 int diff = 0; //预处理 for(int i = 0; i< p.length();i++){ diffArr[p.charAt(i) - 'a']++; diffArr[s.charAt(i) - 'a']--; } for(int i = 0 ; i < 26; i++ ){ if(diffArr[i] != 0){ diff++; } } if(diff == 0){ result.add(0); } for(int l = 0; l < s.length() - p.length(); l++){ int leftIndex = s.charAt(l) - 'a'; if(diffArr[leftIndex] == 0){ diff++; }else if(diffArr[leftIndex] == -1){ diff--; } diffArr[leftIndex]++; int rightIndex = s.charAt(l + p.length()) - 'a'; if(diffArr[rightIndex] == 0){ diff++; }else if(diffArr[rightIndex] == 1){ diff--; } diffArr[rightIndex]--; if(diff == 0){ result.add(l+1); } } return result; } }
与思路1类似,本思路记录窗口中字母类型数量及词频和字符串p的字母类型数量及词频是否相等。
解法一中每次对滑动窗口的检查都不可避免需要检查两个词频数组,复杂度为 O ( C ) O(C) O(C)。
事实上,我们只关心两个数组是否完全一致,因而我们能够只维护一个词频数组 cnt 来实现。
起始处理 p 串时,只对 cnt 进行词频字符自增操作。当处理 s 的滑动窗口子串时,尝试对 cnt 中的词频进行「抵消/恢复」操作:
当滑动窗口的右端点右移时(增加字符),对 cnt 执行右端点字符的「抵消」操作;
当滑动窗口的左端点右移时(减少字符),对 cnt 执行左端点字符的「恢复」操作。
同时,使用变量 a统计 p 中不同字符的数量,使用变量 b统计滑动窗口(子串)内有多少个字符词频与 p 相等。
当滑动窗口移动( 执行「抵消/恢复」)时,如果「抵消」后该字符词频为 0,说明本次右端点右移,多产生了一位词频相同的字符;如果「恢复」后该字符词频数量为 1,说明少了一个为词频相同的字符。当且仅当 a = b 时,我们找到了一个新的异位组。
package com.algorithm.num438; import java.util.LinkedList; import java.util.List; /** * @author hh * @date 2022-2-4 21:20 */ public class Solution3 { public List<Integer> findAnagrams(String s, String p) { List<Integer> result = new LinkedList<>(); //维护窗口的差值 int[] diffArr = new int[26]; int strLength = s.length(); int a = 0,b = 0; //预处理 for(char c : p.toCharArray()){ diffArr[c - 'a']++; } for(int i : diffArr){ if(i > 0){ a++; } } for(int l = 0,r = 0; r < strLength; r++){ int rightIndex = s.charAt(r) - 'a'; if(diffArr[rightIndex] == 1){ //由不同变为相同 b++; } diffArr[rightIndex]--; if(l + p.length() - 1 == r && a == b){ //检测是否为异位词 result.add(l); } while (l + p.length() - 1 <= r){ int leftIndex = s.charAt(l) - 'a'; if(diffArr [leftIndex] == 0){ b--; } diffArr[leftIndex]++; l++; } } return result; } }
请读者自行练习
联系客服