西安网站建设 至诚,html编程教程,设计制作一个保温杯ppt,盐城网站优化目录 滑动窗口算法题目1:长度最小的子数组题目2:无重复字符的最长子串题目3:最大连续1的个数题目4:将x减到0的最小操作数题目5:水果成篮题目6:找到字符串中所有的字母异位词题目7:串联所有单词的子串题目8:最小覆盖子串 滑动窗口算法
滑动窗口的本质还是双指针#xff0c;只不… 目录 滑动窗口算法题目1:长度最小的子数组题目2:无重复字符的最长子串题目3:最大连续1的个数题目4:将x减到0的最小操作数题目5:水果成篮题目6:找到字符串中所有的字母异位词题目7:串联所有单词的子串题目8:最小覆盖子串 滑动窗口算法
滑动窗口的本质还是双指针只不过滑动窗口的双指针是同向双指针两个指针并不回退都是向同一个方向移动如果发现两个指针都可以做到不回退此时可以使用滑动窗口解决问题。
滑动窗口一般的套路就是进窗口判断根据判断结果来决定是否出窗口另外是更新结果更新结果的时机不是固定的要因题而论。
题目1:长度最小的子数组
题目链接209. 长度最小的子数组 - 力扣LeetCode
思路1暴力解法枚举出所有的子数组找出一下长度最小且满足条件的数组
思路1的实现定义left、right两层for循环定义变量sum统计子数组的和下面是伪代码
int len Integer.MAX_VALUE;
for(int left 0;leftnums.length;left){for(int right left;rightnums.length;right){sumnms[right];if(sumtarget){check(len,right-left1);//如果lenright-left1,更新len的值}}
}
return len;分析暴力解法可以发现两个问题当sum满足target要求时right可以停止往后枚举了因为right就算往后枚举sum的要求仍然满足并且子数组的长度是增加的并不符合长度最小这个要求另一个问题是当枚举完一个符合要求的子数组后left是往后移动一位但是right是否有必要再回到left这个位置如果right回退我们又要重新计算sum但是在枚举上一种情况时我们已经计算过和了并不需要重新再计算一次只需要把left位置的值减去即可。所以我们得出结论left和right两个“指针”都只需要往同一个方向移动即可这也就引出今天的主角滑动窗口
思路2滑动窗口定义两个指针left、right维护窗口边界。进窗口操作sumnum[right]进窗口之后判断sum的值是否满足条件如果满足此时需要更新len的结果更新之后出窗口。注意判断操作是循环的因为出窗口之后sum可能还是target需要继续出窗口。
代码实现
class Solution {public int minSubArrayLen(int target, int[] nums) {int left 0,right0;int sum 0;int len Integer.MAX_VALUE;while(rightnums.length){//进窗口:sumnums[right];//判断,需要循环判断,因为left向后移动之后,sum也有可能还targetwhile(sumtarget){//满足条件,更新结果len Math.min(len,right-left1);//出窗口 sum-nums[left];left;}right;}if(lenInteger.MAX_VALUE){return 0;}return len;}
}题目2:无重复字符的最长子串
题目链接3. 无重复字符的最长子串 - 力扣LeetCode 思路1暴力枚举哈希表暴力枚举所有的子串利用哈希表判断子串中是否有重复字符。
思路1的实现定义left、right两层for循环枚举出全部的子串分别判断每个子串是否满足条件下面是伪代码
for(int left0;leftnums.length();left){for(int rightleft;leftnums.length();right){char ch s.charAt(right);if(!hash.contains(ch)){hash.put(ch);} else{//统计.....结果break;}}
}分析暴力解法right位置出现重复字符时,left1right继续回退到left位置但其实right并不需要回退同样的两个指针都是同一个方向移动我们可以使用滑动窗口
思路2滑动窗口进窗口的操作是把字符扔进哈希表判断字符是否在哈希表中已经存在过如果已经存在需要出窗口出窗口之后更新结果
代码实现
class Solution {public int lengthOfLongestSubstring(String s) {char[] chars s.toCharArray();int[] hash new int[128];int left 0;int right 0;int len 0;while(rights.length()){//进窗口hash[chars[right]];while(hash[chars[right]]1) {//说明出现重复字符了,出窗口hash[chars[left]]--;left;}//更新结果len Math.max(len,right-left1);right;}return len;}
}题目3:最大连续1的个数
题目链接1004. 最大连续1的个数 III - 力扣LeetCode 问题转换:找出最长的子数组,0的个数不超过k个
思路1暴力解法计数器枚举出所有的子数组计数器的作用是统计0的个数
思路1的实现伪代码如下
int len 0;
for(int left0;leftnums.length;left){int count 0;for(int rightleft;leftnums.length){if(nums[right]0){count;}if(countk){//更新lenbreak;}}
}分析暴力解法枚举过程中right其实没有必要回退到left位置因为在上一趟遍历中我们已经统计过个数在下一趟遍历的时候我们只需要根据left的位置是否为0来修改count的值因此两个指针都不用回退可以使用滑动窗口的思想
思路2滑动窗口进窗口操作就是统计0的个数接着判断个数是否大于k如果大于k需要出窗口出完窗口之后才更新结果因为出窗口后k的个数才满足要求。
代码实现
class Solution {public int longestOnes(int[] nums, int k) {int count 0;int left 0, right 0;int len 0;while (right nums.length) {// 进窗口if (nums[right] 0) {count;}// 判断while (count k) {// 需要出窗口if (nums[left] 0) {count--;}left;}// 更新结果len Math.max(len, right - left 1);right;}return len;}
}题目4:将x减到0的最小操作数
题目链接1658. 将 x 减到 0 的最小操作数 - 力扣LeetCode 分析题目要求 如图题目要我们返回的值是ab长度为a的子数组与长度为b的子数组元素之和恰好为x并且ab的值是最小的正难则反我们可以先求出n-(ab)。
问题转换求出最长的子数组的长度len子数组满足元素之和恰好为sum-xsum为原数组nums的元素之和求出这个长度值之后直接返回n-len即可
思路1暴力解法枚举出所有的子数组求出满足条件的长度最长的子数组即可
思路1的实现伪代码如下
int len 0;
int curSum 0;
for(int left 0;leftnums.length;left){for(int rightleft;rightnums.length;right){if(curSumsum-x){//更新lenbreak;}}
}
return n-len;思路2滑动窗口
class Solution {public int minOperations(int[] nums, int x) {int sum 0;for (int i : nums) {sum i;}int len -1;int n nums.length;int target sum - x;int left 0, right 0;int curSum 0;while (right n) {// 进窗口curSum nums[right];while (curSum target left n) {//left可能越界 // 如果curSumtarget,需要出窗口curSum - nums[left];left;}// 出完窗口之后,此时的结果才可能是正确的,// 更新结果if (curSum target) {len Math.max(len, right - left 1);}right;}if (len -1) {return -1;}return n - len;}
}题目5:水果成篮
题目链接904. 水果成篮 - 力扣LeetCode
问题转换求最长的子数组的长度子数组满足水果的种类2
思路1暴力解法哈希表暴力枚举出所有的子数组借助哈希表、计数器来判断水果种类是否超过2
思路2滑动窗口哈希表 代码实现
class Solution {public int totalFruit(int[] fruits) {int n fruits.length;int[] hash new int[n 1];// 构建哈希表int left 0, right 0;int count 0;int len 0;while (right n) {// 进窗口if (hash[fruits[right]] 0) {count;}hash[fruits[right]];while (count 2) {// 出窗口hash[fruits[left]]--;if (hash[fruits[left]] 0) {count--;//移出哈希表}left;}// 更新结果len Math.max(len, right - left 1);right;}return len;}
}题目6:找到字符串中所有的字母异位词
题目链接438. 找到字符串中所有字母异位词 - 力扣LeetCode 思路1暴力解法先把p字符串的词频字符出现的个数丢进哈希表中接着枚举字符串s枚举出所有长度为len(字符串p的长度)的子串每枚举一个子串就把该子串丢进一个哈希表中比较两个哈希表对应字符的频次
思路2滑动窗口哈希表进窗口的操作把字符扔进哈希表中何时出窗口?当right位置和left位置长度大于p字符串的长度此时要出窗口因为这道题的窗口大小是固定的窗口大小就是p字符串的长度出完窗口后比较两个哈希表的内容如果内容相同就把结果扔进集合中 代码实现
class Solution {public ListInteger findAnagrams(String s, String p) {ListInteger ret new ArrayList();int[] hash1 new int[26];int[] hash2 new int[26];//把p的字符频次扔进哈希表hash2中for (int i 0; i p.length(); i) {char ch p.charAt(i);hash2[ch - a];}//滑动窗口int left 0, right 0;while (right s.length()) {//进窗口char in s.charAt(right);hash1[in-a];//判断if (right - left 1 p.length()) {//出窗口char out s.charAt(left);hash1[out-a]--;left;}//更新结果//比较两个哈希表boolean flg true;for (int i 0; i 26; i) {if (hash1[i] ! hash2[i]) {//两个哈希表内容不同,不是想要的结果flg false;}}if (flg) {ret.add(left);}right;}return ret; }
}优化更新结果这里比较两个哈希表需要遍历一遍哈希表通过一个变量count可以优化这个操作count表示的是有效字符的个数什么是有效字符也就是p字符串出现过的字符
核心逻辑
//进窗口操作
//.....//进窗口后
if(hash1[in]hash2[in]){count;
}//.....//出窗口前
if(hash1[in]hash2[in]){count--;
}//出窗口
in和out表示要进窗口、出窗口的字符
代码实现
class Solution {public ListInteger findAnagrams(String s, String p) {ListInteger ret new ArrayList();//哈希表长度26-题目说明了只有小写字母int[] hash1 new int[26];int[] hash2 new int[26];//p的哈希表for (int i 0; i p.length(); i) {char ch p.charAt(i);hash2[ch - a];//a-0,b-1,c-2.........}//双指针int left 0, right 0;int count 0;//统计窗口中有效字符的个数while (right s.length()) {//进窗口char in s.charAt(right);hash1[in - a];if (hash1[in - a] hash2[in - a]) {count;}//判断if (right - left 1 p.length()) {//需要出窗口char out s.charAt(left);if (hash1[out - a] hash2[out - a]) {count--;}hash1[out - a]--;left;}if (count p.length()) {ret.add(left);}right;}return ret;}
}题目7:串联所有单词的子串
题目链接30. 串联所有单词的子串 - 力扣LeetCode
思路滑动窗口哈希表
这道题的思路和上一道题找到字符串中所有的字母异位词其实是一样的为什么
如果把字符串看成一个字母如图是不是就变成了找到字符串中所有的字母异位词这个问题
不同点
1、哈希表创建的哈希表是String,Integer类型的
2、left和right指针的移动每次移动lenwords中字符串的长度
3、滑动窗口的执行次数执行len次
代码实现
class Solution {public ListInteger findSubstring(String s, String[] words) {ListInteger ret new ArrayList();//1. 把words扔进哈希表中HashMapString, Integer hash new HashMap();for (int i 0; i words.length; i) {hash.put(words[i], hash.getOrDefault(words[i], 0) 1);}int len words[0].length();//执行len次滑动窗口for (int i 0; i len; i) {int left i, right i;int count 0;//有效字符串的个数HashMapString, Integer hashMap new HashMap();//滑动窗口while (right len s.length()) {//进窗口维护countString in s.substring(right, right len);hashMap.put(in, hashMap.getOrDefault(in, 0) 1);if (hashMap.get(in) hash.getOrDefault(in, 0)) {count;}//判断while ((right - left 1) len * words.length) {//需要出窗口维护countString out s.substring(left, left len);if (hashMap.get(out) hash.getOrDefault(out, 0)) {count--;}hashMap.put(out, hashMap.get(out) - 1);left len;}if (count words.length) {ret.add(left);}right len;}}return ret; }
}题目8:最小覆盖子串
题目链接76. 最小覆盖子串 - 力扣LeetCode 解法滑动窗口哈希表进窗口的操作就是让left位置的字符进入哈希表在进窗口之后维护kinds(字符种类个数)当两个哈希表中有效字符的种类相等时此时要出窗口出窗口之前维护kinds 代码实现
class Solution {public String minWindow(String ss, String tt) {// 数组模拟哈希表int[] hash1 new int[128];int[] hash2 new int[128];// 保存t的频次char[] s ss.toCharArray();char[] t tt.toCharArray();int count 0;// t字符串中字符种类个数// 保存t的频次for (char ch : t) {if (hash2[ch] 0) {count;}hash2[ch];}// 滑动窗口启动int left 0, right 0, kinds 0;int minLen Integer.MAX_VALUE, begin -1;while (right s.length) {// 进窗口维护kindschar in s[right];hash1[in];// 维护有效字符种类if (hash1[in] hash2[in]) {kinds;}// 判断,如果kindscount,也就是说hash1有效字符种类和hash2一样while (kinds count) {// 更新结果,起始位置和最短长度if (right - left 1 minLen) {minLen right - left 1;begin left;}// 出窗口维护kindschar out s[left];// 出之前判断有效字符种类if (hash1[out] hash2[out]) {kinds--;}//出窗口hash1[out]--;left;}right;}if (begin -1) {return new String();}return ss.substring(begin, begin minLen);}
}
