算法介绍
滑动窗口算法来自tcp协议的一种特性,它的高效使得其也变成了算法题的一种重要考点.滑动窗口的实现实际上也是通过两个指针前后遍历集合实现,但是因为它有固定的解题格式,我将其单独做成一个篇章.
滑动窗口的解题格式:
首先,定义两个指针left和right,与双指针不同的是,它们一开始都指向同一个地方(通常是数组中的第一个元素).
接着,让right指针后移,把right指针指向的元素"进窗口".
随后,判断当前"窗口"是否满足题目要求.
最后,如果不满足条件就要让left指针指向的元素"出窗口",left指针再后移.
上述解题格式中不难发现,"窗口"实际上就是一个连续的区间,滑动窗口算法主要用来处理某个连续区间上的问题,左右指针同步遍历将O(n^2)的时间复杂度降低为O(n),是一种十分高效,巧妙的算法.
习题讲解
1. 长度最小的子数组
209. 长度最小的子数组
题目解析
难点:
要求出所有满足条件中的子数组中最短的长度,难以使用暴力的方式求解.
算法应用:
子数组:在给定数组中连续取出某个区间得到的数组.这题就是求这个区间的最短长度,就可以使用滑动窗口算法进行解答.定义两个指针left和right,指向数组的第一个元素.由于这题关注某个连续区间的和的具体大小,需要定义一个sum变量维护区间上的和,一个ret变量记录答案.
进窗口: right指针指向的元素直接进窗口(sum+=nums[right])一般来说滑动窗口算法中,入窗口的限制条件十分少.
判断+出窗口: 如果当前的区间和小于target(不满足题目答案要求),不用更新答案,直接后移right指针即可;如果当前的区间和大于等于target(因为我们要求最小的区间长度,为了求这个最优解,应该确保窗口内的和尽量保持在小于target,需要出窗口,否则在本题下得到的必定不是最优解),一边更新答案,维护sum变量的值,一边出窗口(sum-=nums[left]),并将left指针右移,直到区间内的和小于target.
操作细节:
记录答案的ret变量初始化应该为最大值,最后返回时判断其是否仍为最大值,若还是最大值,需要返回0代替.
出窗口时,需要使用while循环而非if判断,虽然"进窗口"是一次循环只有一个元素进入,但是"出窗口"并没有这个限制,需要关注题目的具体条件,"出窗口"一定要"出到不能再出为止".
代码实现:
public int minSubArrayLen(int target, int[] nums) {
int sum = 0;
int ret = Integer.MAX_VALUE;
for(int left=0,right=0; right<nums.length; right++) {
sum += nums[right];
while (sum >= target) {
ret = Math.min(ret,right-left+1);
sum -= nums[left];
left++;
}
}
return ret == Integer.MAX_VALUE ? 0 : ret;
}2. 无重复字符的最长字串
3. 无重复字符的最长字串
题目解析
难点:
要求出所有满足条件中的字串中最长的长度,难以使用暴力的方式求解,这道题和上道题十分相似,可以自己先行尝试.
算法应用:
子串:在给定字符串中连续取出某个区间得到的字符串.这题就是求这个区间的最长长度,就可以使用滑动窗口算法进行解答.为了方便,我们先将字符串转为字符数组.
定义两个指针left和right,指向数组的第一个元素.这题关注某个连续区间内不能有重复字符串,需要定义一个哈希表(用数组模拟)记录区间内出现的字符及其次数,一个ret变量记录答案.
进窗口: right指针指向的元素直接进窗口(哈希表进行记录).
判断+出窗口: 如果当前的区间内有重复字符就需要出窗口,但是我们出窗口的判断在每一次循环中都会执行,如果本次出现了重复的字符,只可能是s[right]这个字符重复了(本次循环中只有这一个媳妇进了窗口,而在进窗口前我们又保证了窗口内没有重复元素).那我们就要出窗口找到上一个出现的s[right]字符,直到将它出窗口后,这个过程才结束.出窗口过程中要不断维护哈希表.直到出窗口结束,才能更新ret的值,这题与上题的不同之处就在此,上题是出窗口到"不满足答案条件的窗口"为止,本题是出窗口到"满足答案条件的窗口"为止,这就是求最短与最长区间长度的区别.
操作细节:
使用数组模拟哈希表,由于字符串中有字母以外的字符,需要定义一个足够长的数组,防止越界.
由于求最长的满足条件字串的长度,ret在定义时初始化为0,更新时注意字串长度为right-left+1.
代码实现:
public int lengthOfLongestSubstring(String ss) {
int[] hash = new int[128];
char[] s = ss.toCharArray();
int ret = 0;
for (int left=0,right=0; right<s.length; right++) {
hash[s[right]]++;
while (hash[s[right]]>1) {
hash[s[left]]--;
left++;
}
ret = Math.max(ret,right-left+1);
}
return ret;
}3. 最大连续1的个数lll
1004. 最大连续1的个数lll
题目解析
难点:
这道题的难点在于逆向思维,如果去思考如何翻转0是十分复杂的.
算法应用:
我们可以不去实际地进行翻转操作,而是将问题转化为: 求一个最长连续的区间的长度,其中包含0的个数不超过k个.这样我们就又可以使用滑动窗口算法进行解答.定义一个zero变量来记录窗口内包含的0的个数.
进窗口: right指针右移,如果nums[right]等于0,zero++.
判断+出窗口: 如果zero>k,如果nums[left]等于0,zero--,left指针右移.
更新答案ret.
操作细节:
更新答案ret时,注意区间长度为right-left+1.
代码实现:
public int longestOnes(int[] nums, int k) {
int len = 0,zero = 0,n = nums.length;
for(int left = 0,right = 0;right<n;right++) {
if(nums[right]==0) zero++;
while(zero>k) {
if(nums[left]==0) zero--;
left++;
}
len = Math.max(len,right-left+1);
}
return len;
}4. 将x减少到0的最少操作数
1658. 将x减少到0的最少操作数
题目解析
难点:
这道题目中告诉我们,减少的规则是对数组两端进行减少操作,但是我们并不知道到底是操作左边还是右边,那么就需要使用到逆向思维.
算法应用:
题目要求我们一共减少x(所有减少元素的和为x),所使用的操作数(也就是减少的元素的个数).我们可以将其转化为:求一个区间和为 target=sum-x 的区间的最长长度(sum是初始数组中所有元素的和),拿原始数组长度减去这个最长长度就得到了我们需要的"最少操作数".
这里仍然使用sum变量记录区间内元素的和,使用前需要置0.(sum = 0)
进窗口: sum += nums[right].
出窗口: 如果sum > target,原因是我们需要找和为target的区间,如果大于target还不出窗口,后面的元素又都是正的,相加必然只会导致sum越来越大,不可能趋近等于target,出窗口直到sum<=target.
判断: 由题意,当sum = target时,才更新答案ret.
操作细节:
计算target=sum - x时,如果target<0,直接返回-1,因为题目条件中:每个元素都大于0,不可能有几个正数相加得到一个负数.但是target=0是合法的,可以通过减少所有的元素得到.
ret初始化的值为-1,如果最后ret值仍为-1,直接返回-1,说明不存在满足题意的情况;如果不是-1,记得返回n-ret(n为原始数组的长度),因为我们是你想思维进行解题的.
更新答案ret时,注意区间长度为right-left+1.
代码实现:
public int minOperations(int[] nums, int x) {
int sum = 0,n = nums.length;
for (int num : nums) sum += num;
int target = sum - x;
if (target<0) return -1;
int ret = -1;
sum = 0;
for (int left=0,right=0; right<n; right++) {
sum += nums[right];
while (sum>target) {
sum -= nums[left];
left++;
}
if (sum == target) {
ret = Math.max(ret, right-left+1);
}
}
return ret == -1 ? -1 : n-ret;
}5. 水果成篮
904. 水果成篮
题目解析
难点:
这道题目相比前面的题目多了一些判断操作,但是读者可以根据前面的讲解,先自行尝试.
提示:要考虑维护窗口内水果种类的数量.
算法应用:
题目要求我们去求一个最长区间的长度,在这个区间内至多只能有两种水果.我们就需要定义一个哈希表(数组模拟)来记录窗口内各种水果出现的次数,同时需要定义一个kind变量维护水果的种类数量.
fruits[i]是某一种水果,hash[fruits[i]]是fruits[i]这种水果在窗口内出现的次数.
判断+进窗口: 先判断hash[fruits[right]]的值是否为0,如果为0,说明水果的种类在当前窗口内没出现过,再增加hash[fruits[right]]的值,维护kind变量(kind++).
出窗口+判断: 如果kind>2(超出水果篮子的数量)就需要进行出窗口操作.这时,需要注意我们是先去减少hash[fruits[left]]的值,再去判断是否减少到0,如果减少到0,说明fruits[left]这种水果在进行出窗口操作后不再出现在当前窗口中,维护kind变量(kind--).(如果调换这个顺序,读者可以自行探究会发生什么).
更新答案ret的值.
调换顺序的情况:
如果先进窗口(hash[fruits[right]]++)再判断hash[fruits[right]]的值是否为0,就会发现进窗口的水果,都已存在再窗口中,kind不会++;如果先判断hash[fruits[left]]的值是否为0再出窗口(hash[fruits[left]]--),就会发现出窗口的水果,都仍存在在窗口中,kind不会--.
操作细节:
这道题的判断与操作先后顺序十分重要,如果顺序颠倒,kind变量就不能得到正确的维护,继而得不到正确答案.
这道题中元素的数值仅仅表示不同种类的水果,而不是水果的个数.
更新答案ret时,注意区间长度为right-left+1.
代码实现:
public int totalFruit(int[] fruits) {
int n = fruits.length;
int kind = 0;
int ret = 0;
int[] hash = new int[100000];
for (int left=0,right=0; right<n; right++) {
int in = fruits[right];
//进窗口,先判断再加
if (hash[in]++==0) kind++;
while (kind>2) {
int out = fruits[left];
left++;
//出窗口,先减再判断
if (--hash[out]==0) kind--;
}
ret = Math.max(ret, right-left+1);
}
return ret;
}6. 找到字符串中所有字母异位词
438. 找到字符串中所有字母异位词
题目解析
难点:
这道题目要求我们在字符串s的子串中,找出所有与字符串p的构成异位词的子串,要返回满足要求的子串的起始索引.这个过程实际上比较复杂,但是仔细思考一下,仍然是要解决一个连续区间上的存在性问题,可以使用滑动窗口算法解决.
算法应用:
首先,我们需要使用一个哈希表hash1,记录下字符串p中包含哪些字符.接着,需要再定义一个哈希表hash2记录窗口内出现的字符次数.我们还另外需要一个变量count,记录当前窗口内的字符中,能对构成p的异位词有用的字符数量.
进窗口+判断: right指针右移,hash2[s[right]]++,如果hash2[s[right]]<=hash1[s[right]](说明s[right]对构成p的异位词有用),count++.
判断+出窗口: 如果区间长度超过了p的长度,那么一定构不成异位词(互为异位词的字符串长度肯定相等),需要进行出窗口操作.如果hash2[s[left]]<=hash1[s[left]](说明s[right]对构成p的异位词有用)，count--,hash2[s[left]]--,left指针右移.
如果count等于p的长度(说明窗口内所有字符都对构成p的异位词有用，这时窗口内的子串就是p的异位词).在ret中记录下left(开始索引).
操作细节:
为了便于操作,将s和p都转为字符数组进行操作.
s和p中只有小写字母字符,为了节省空间与便捷,使用长度为26的数组模拟哈希表.
在本题中,仍然需要注意hash2[]值的增减与判断是否字符对构成异位词有用,两者之间先后顺序的判断.
代码实现:
public List<Integer> findAnagrams(String ss, String pp) {
List<Integer> ret = new ArrayList<>();
char[] s = ss.toCharArray();
char[] p = pp.toCharArray();
int[] hash1 = new int[26];
int[] hash2 = new int[26];
int n = s.length,m = p.length,count = 0;
for(char c:p) {
hash1[c-'a']++;
}
for(int left = 0,right = 0;right<n;right++) {
char in = s[right];
hash2[in-'a']++;
if(hash2[in-'a']<=hash1[in-'a']) count++;
if(right-left+1>m) {
char out = s[left];
if(hash2[out-'a']--<=hash1[out-'a']) {
count--;
}
left++;
}
if(count==m) ret.add(left);
}
return ret;
}7. 串联所有单词的子串
30. 串联所有单词的子串
题目解析
难点:
这道题相较于上一道题,异位词变成了异位字符串,把基本单位从上一题中的字符变成了给定的字符串.但是在操作过程中,还是有许多细节需要注意.
算法应用:
首先,我们需要使用一个哈希表hash1,记录下字符串集words中包含哪些字符串.接着,需要再定义一个哈希表hash2记录窗口内出现的字符串及其出现次数.我们还另外需要一个变量count,记录当前窗口内的字符串中,能对构成满足要求的子串有用的字符串数量.
外层循环: 我们一共要执行len次(len是words中的字符串的长度),因为我们也不知道符合要求的子串到底是从原字符串哪个下标开始的,所以需要去分别执行len次滑动窗口算法.那么len位置后面位置的下标为什么不用遍历呢?因为我们每次指针后移都是后移len,而不是1,len下标后面的位置都可以通过[0,len-1]中的下标跳过len后得到,这与我们将len长度的字符串视为一个基本单位的思想相符.
进窗口+判断: right指针右移len位,hash2记录下对应字符串(String in=s.substring(right，right+len))及其出现次数,如果hash2中in的对应值<=hash1中in的对应值(说明in对构成满足题意的子串有用),count++.
判断+出窗口: 如果区间长度超过了words中所有字符串的长度之和(words中字符串长度相等,长度之和即len*m,m是words中字符串的个数),那么一定构不成满足题意的子串(串联所有单词的字符串长度肯定与len*m相等),需要进行出窗口操作.(String out = s.substring(left，left+len)).如果hash2中out对应的值<=hash1中out对应的值(说明out对构成满足题意的子串有用),count--,hash2中对应out的值减少,left指针右移len个单位.
如果count等于words中所有字符串的个数m(说明窗口内所有字符串都对构成串联所有单词的子串有用,这时窗口内的子串就是串联所有单词的子串),在ret中记录下left(开始索引).
操作细节:
本题中不能使用数组模拟哈希表,因为其中映射关系是字符串到整型的映射.
在使用hash1记录words中的字符串时,注意可能出现重复,需要对此进行处理.
滑动窗口的循环执行时,left和right指针要初始化为i(i为外层循环的控制变量),循环结束条件是right+len<=s.length(),否则将漏解或者指针越界.
代码实现:
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> ret = new ArrayList<>();
Map<String, Integer> hash1 = new HashMap<>();
for (String word : words) hash1.put(word,hash1.getOrDefault(word, 0)+1);//注意可能重复
int len = words[0].length(),m = words.length,n = s.length();
for (int i=0; i<len; i++) {
Map<String, Integer> hash2 = new HashMap<>();
int count = 0;
//注意循环终止条件(right+len<=n)
for (int left=i,right=i; right+len<=n; right+=len) {
String in = s.substring(right, right+len);
hash2.put(in, hash2.getOrDefault(in, 0)+1);
if (hash2.get(in) <= hash1.getOrDefault(in, 0)) count++;
if (right-left+1 > len*m) {
String out = s.substring(left, left+len);
if (hash2.get(out) <= hash1.getOrDefault(out, 0)) count--;
hash2.put(out, hash2.get(out)-1);
left+=len;
}
if (count == m) ret.add(left);
}
}
return ret;
}8. 最小覆盖字串
76. 最小覆盖字串
题目解析
难点:
做过了这么多题目,这道题不难想到需要使用两个哈希表来分别记录窗口内的字符和给定字符串中的字符,但是这道题作为hard题还是有难度的.
算法应用:
首先,我们需要使用一个哈希表hash1,记录下给定字符串t中包含哪些字符.接着,需要再定义一个哈希表hash2记录窗口内出现的字符及其出现次数.我们还另外需要一个变量count,记录当前窗口内的字符中,可以用来构成最小覆盖字串字符种类的数量(count的更新策略十分关键,在后文会详解).(这里与上一题不同,记录的是字符种类的数量),一个kinds变量来记录t中字符种类的数量.由于题目要求的时一个具体的字串,需要retIndex变量记录下这个字串的起始索引,retLen变量记录它的长度,这两个变量就能唯一确定一个子串.
进窗口+判断: right指针右移,hash2记录下对应字符及其出现次数(hash2[in]++),如果hash2[in]==hash1[in](说明当前窗口中in这种字符正好可以满足t对于in这种字符的需求,可以用来构成最小覆盖字串.一定要注意判断条件是相等!),count++.
判断+出窗口: 如果count == kinds,说明一定构成了满足题意的子串,更新retIndex和retLen(这两个变量是同步更新的,要么一起更新,要么都不更新,因为在不断出窗口,len变化时,left也在右移变化),再进行出窗口操作.如果hash2[out]==hash1[out](说明当前窗口中out这种字符正好可以满足t对于out这种字符的需求,可以用来构成最小覆盖字串),count--,hash2[out]--,left指针右移,直到count不再与kinds相等.
最后,判断是否存在.若存在,则根据retIndex和retLen两个变量截取s的字串返回,否则返回空串.
操作细节:
本题中可以使用数组模拟哈希表.
将retLen变量初始化为最大值,最后将retLen是否仍为最大值来作为判断是否存在满足题意的字串的条件.
代码实现:
public String minWindow(String s, String tt) {
char[] t = tt.toCharArray();
int[] hash1 = new int[128];
int kinds = 0;
for (char c : t) {
if (hash1[c]++ == 0) {
kinds++;
}
}
int[] hash2 = new int[128];
int retIndex = 0, retLen = Integer.MAX_VALUE, count = 0;
for (int left=0,right=0; right<s.length(); right++) {
char in = s.charAt(right);
if (++hash2[in] == hash1[in]) count++;
while (count == kinds) {
if (right-left+1<retLen) {
retLen = right-left+1;
retIndex = left;
}
char out = s.charAt(left);
left++;
if (hash2[out]--==hash1[out]) {
count--;
}
}
}
return retLen == Integer.MAX_VALUE ? "" : s.substring(retIndex, retIndex+retLen);
}
