【問(wèn)題描述】[第76題][最小覆蓋子串][中等]

給你一個(gè)字符串 S、一個(gè)字符串 T，請(qǐng)?jiān)谧址?S 里面找出：包含 T 所有字符的最小子串。示例：輸入: S = "ADOBECODEBANC", T = "ABC" 輸出: "BANC" 說(shuō)明：如果 S 中不存這樣的子串，則返回空字符串 ""。 如果 S 中存在這樣的子串，我們保證它是唯一的答案。

【解答思路】

1. 滑動(dòng)窗口 map

時(shí)間復(fù)雜度：O(N^2) 空間復(fù)雜度：O(1)

class Solution {public String minWindow(String s, String t) {if (s == null || t == null || s.length() == 0 || t.length() == 0) return "";// 定義一個(gè)數(shù)字，用來(lái)記錄字符串 t 中出現(xiàn)字符的頻率，也就是窗口內(nèi)需要匹配的字符和相應(yīng)的頻率int[] map = new int[128];for (char c : t.toCharArray()) {map[c]++;}int left = 0, right = 0;int match = 0; // 匹配字符的個(gè)數(shù)int minLen = s.length() + 1; // 最大的子串的長(zhǎng)度// 子串的起始位置 子串結(jié)束的位置(如果不存在這樣的子串的話，start，end 都是 0，s.substring 截取就是 “”int start = 0, end = 0;while (right < s.length()){char charRight = s.charAt(right); // 右邊界的那個(gè)字符map[charRight]--; // 可以理解為需要匹配的字符 charRight 減少了一個(gè)// 如果字符 charRight 在 t 中存在，那么經(jīng)過(guò)這一次操作，只要個(gè)數(shù)大于等于 0，說(shuō)明匹配了一個(gè)// 若字符 charRight 不在 t 中，那么 map[charRight] < 0, 不進(jìn)行任何操作if (map[charRight] >= 0) match++;right++; // 右邊界右移，這樣下面就變成了 [)，方便計(jì)算窗口大小// 只要窗口內(nèi)匹配的字符達(dá)到了要求，右邊界固定，左邊界收縮while (match == t.length()){int size = right - left;if (size < minLen){minLen = size;start = left;end = right;}char charLeft = s.charAt(left); // 左邊的那個(gè)字符map[charLeft]++; // 左邊的字符要移出窗口// 不在 t 中出現(xiàn)的字符，移出窗口，最終能夠達(dá)到的最大值 map[charLeft] = 0// 如果恰好移出了需要匹配的一個(gè)字符，那么這里 map[charLeft] > 0, 也就是還要匹配字符 charLeft，此時(shí) match--if (map[charLeft] > 0) match--;left++; // 左邊界收縮}}return s.substring(start, end);} }

2. 互動(dòng)窗口 漢明距離

時(shí)間復(fù)雜度：O(N) 空間復(fù)雜度：O(1)

【總結(jié)】

1.滑動(dòng)窗口算法模板

/* 滑動(dòng)窗口算法框架 */ 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++;// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新.../*** debug 輸出的位置 ***/printf("window: [%d, %d)\n", left, right);/********************/// 判斷左側(cè)窗口是否要收縮while (window needs shrink) {// d 是將移出窗口的字符char d = s[left];// 左移窗口left++;// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新...}} }

2.滑動(dòng)窗口 end指針向右移動(dòng)， start向左移動(dòng) 細(xì)節(jié)多多

3.細(xì)節(jié)

// 分類· int[] map = new int[128];for (char c : t.toCharArray()) {map[c]++;}

轉(zhuǎn)載https://leetcode-cn.com/problems/minimum-window-substring/solution/java-yi-ge-shu-zu-ji-lu-pin-shu-de-hua-dong-chuang/

參考鏈接：https://leetcode-cn.com/problems/minimum-window-substring/solution/hua-dong-chuang-kou-suan-fa-tong-yong-si-xiang-by-/

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的[Leedcode][JAVA][第76题][最小覆盖子串]滑动窗口]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。