基础算法练习--滑动窗口(日更中)
算法介绍
滑动窗口算法来自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. 将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;
}4. 水果成篮
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;
}