算法及数据结构系列 - 滑动窗口

系列文章目录

算法及数据结构系列 - 二分查找
算法及数据结构系列 - BFS算法
算法及数据结构系列 - 动态规划
算法及数据结构系列 - 双指针
算法及数据结构系列 - 回溯算法
算法及数据结构系列 - 树

滑动窗口

框架思路

/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {unordered_map<char, int> need, window;for (char c : t) need[c]++;int left = 0, right = 0;int valid = 0; while (right < s.size()) {// c 是将移入窗口的字符char c = s[right];// 右移窗口right++;// 进行窗口内数据的一系列更新.../*** debug 输出的位置 ***/printf("window: [%d, %d)\n", left, right);/********************/// 判断左侧窗口是否要收缩while (window needs shrink) {// d 是将移出窗口的字符char d = s[left];// 左移窗口left++;// 进行窗口内数据的一系列更新...}}
}

经典题型

76. 最小覆盖子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：

输入: S = “ADOBECODEBANC”, T = “ABC”
输出: “BANC”
说明：

如果 S 中不存这样的子串，则返回空字符串 “”。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

提示：通过valid记录满足条件的字符数;只关注need中的字符
注意: Integer 类型比较 不能用 == ！！！！, 要用 equals()

class Solution {public String minWindow(String s, String t) {int left = 0, right = 0;Map<Character, Integer> win = new HashMap<Character, Integer>();Map<Character, Integer> need = new HashMap<Character, Integer>();for(int i = 0; i< t.length(); i++){need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);}int valid = 0;int start = -1, len = Integer.MAX_VALUE;while(right < s.length()){char c = s.charAt(right);right ++;if(need.containsKey(c)){win.put(c, win.getOrDefault(c, 0) + 1);if(win.get(c).equals( need.get(c))){ // 注意：不能用 ==valid ++;}}while(valid == need.size()){if(right - left < len){start = left;len = right - left;}char d = s.charAt(left);left++;if(need.containsKey(d)){if(win.get(d).equals(need.get(d))){valid --;}win.put(d, win.get(d) - 1);}}}return start == -1? "":s.substring(start, start + len);}
}

567. 字符串的排列

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例1:

输入: s1 = "ab" s2 = "eidbaooo"  
输出: True  
解释: s2 包含 s1 的排列之一 ("ba").  

示例2:

输入: s1= "ab" s2 = "eidboaoo"
输出: False

class Solution {public boolean checkInclusion(String s1, String s2) {int left = 0, right = 0;int[] win = new int[256];int[] need = new int[256];int needCharSize = 0;for(int i = 0 ; i< s1.length(); i++){if (need[s1.charAt(i)] == 0){needCharSize++;}need[s1.charAt(i)] ++;}int valid = 0;while(right < s2.length()){char c = s2.charAt(right);right++;if(need[c] > 0){win[c]++;if(need[c] == win[c]){valid++;}}while(valid == needCharSize){if(right - left == s1.length()){return true;}char d = s2.charAt(left);left++;if(need[d] > 0){if(need[d] == win[d]){valid--;}win[d]--;}}}return false;}
}

438. 找到字符串中所有字母异位词

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。

class Solution {List<Integer> res = new ArrayList<Integer>();public List<Integer> findAnagrams(String s, String p) {int left = 0, right = 0;int[] win = new int[256];int[] need = new int[256];int needCharSize = 0;for(int i = 0; i< p.length();i++){char c = p.charAt(i);if(need[c] == 0){needCharSize++;}need[c]++;}int valid = 0;while(right < s.length()){char c = s.charAt(right);right++;if(need[c] > 0){win[c] ++;if(win[c] == need[c]){valid ++;}}while(valid == needCharSize){if(right - left == p.length()){res.add(left);}char d = s.charAt(left);left++;if(need[d] > 0){if(need[d] == win[d]){valid --;}win[d] --;}}}return res;}
}

3. 无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

class Solution {public int lengthOfLongestSubstring(String s) {int left = 0, right = 0;int[] win = new int[256];int res = 0;while(right < s.length()){char c = s.charAt(right);right++;win[c]++;while(win[c] > 1){// 收缩以满足条件char d = s.charAt(left);left++;win[d]--;}// 满足条件更新结果res = Math.max(res, right - left);}return res;}
}