基础算法练习--滑动窗口(日更中)
算法介绍
滑动窗口算法来自tcp协议的一种特性,它的高效使得其也变成了算法题的一种重要考点.滑动窗口的实现实际上也是通过两个指针前后遍历集合实现,但是因为它有固定的解题格式,我将其单独做成一个篇章.
滑动窗口的解题格式:
首先,定义两个指针left和right,与双指针不同的是,它们一开始都指向同一个地方(通常是数组中的第一个元素).
接着,让right指针后移,把right指针指向的元素"进窗口".
随后,判断当前"窗口"是否满足题目要求.
最后,如果不满足条件就要让left指针指向的元素"出窗口",left指针再后移.
上述解题格式中不难发现,"窗口"实际上就是一个连续的区间,滑动窗口算法主要用来处理某个连续区间上的问题,左右指针同步遍历将O(n^2)的时间复杂度降低为O(n),是一种十分高效,巧妙的算法.
习题讲解
1. 长度最小的子数组
题目解析
难点:
要求出所有满足条件中的子数组中最短的长度,难以使用暴力的方式求解.
算法应用:
子数组:在给定数组中连续取出某个区间得到的数组.这题就是求这个区间的最短长度,就可以使用滑动窗口算法进行解答.定义两个指针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. 无重复字符的最长字串
题目解析
难点:
要求出所有满足条件中的字串中最长的长度,难以使用暴力的方式求解,这道题和上道题十分相似,可以自己先行尝试.
算法应用:
子串:在给定字符串中连续取出某个区间得到的字符串.这题就是求这个区间的最长长度,就可以使用滑动窗口算法进行解答.为了方便,我们先将字符串转为字符数组.
定义两个指针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;
}原文地址：https://blog.csdn.net/ling_zu_qi/article/details/143551541
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！