系列文章目錄

算法及數據結構系列 - 二分查找
算法及數據結構系列 - 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;}
}