給你一個(gè)字符串 S、一個(gè)字符串 T，請(qǐng)?jiān)谧址?S 里面找出：包含 T 所有字母的最小子串。

示例：

輸入: S = "ADOBECODEBANC", T = "ABC"
輸出: "BANC"
說明：

如果 S 中不存這樣的子串，則返回空字符串 ""。
如果 S 中存在這樣的子串，我們保證它是唯一的答案。

思路：雙指針，兩個(gè)指針中間代表一個(gè)字符串。

都往右邊走，滿足條件就左指針向右（縮），不滿足條件就右指針向右（擴(kuò)）

public String minWindow(String s, String t) {int[] map = new int[128];// 遍歷字符串 t，初始化每個(gè)字母的次數(shù)for (int i = 0; i < t.length(); i++) {char char_i = t.charAt(i);map[char_i]++;}int left = 0; // 左指針int right = 0; // 右指針int ans_left = 0; // 保存最小窗口的左邊界int ans_right = -1; // 保存最小窗口的右邊界int ans_len = Integer.MAX_VALUE; // 當(dāng)前最小窗口的長度int count = t.length();// 遍歷字符串 swhile (right < s.length()) {char char_right = s.charAt(right);// 當(dāng)前的字母次數(shù)減一map[char_right]--;//代表當(dāng)前符合了一個(gè)字母if (map[char_right] >= 0) {count--;}// 開始移動(dòng)左指針，減小窗口while (count == 0) { // 如果當(dāng)前窗口包含所有字母，就進(jìn)入循環(huán)// 當(dāng)前窗口大小int temp_len = right - left + 1;// 如果當(dāng)前窗口更小，則更新相應(yīng)變量if (temp_len < ans_len) {ans_left = left;ans_right = right;ans_len = temp_len;}// 得到左指針的字母char key = s.charAt(left);// 因?yàn)橐旬?dāng)前字母移除，所有相應(yīng)次數(shù)要加 1map[key]++;//此時(shí)的 map[key] 大于 0 了，表示缺少當(dāng)前字母了，count++if (map[key] > 0) {count++;}left++; // 左指針右移}// 右指針右移擴(kuò)大窗口right++;}return s.substring(ans_left, ans_right + 1); }

總結(jié)

以上是生活随笔為你收集整理的leetcode76 最小覆盖子串的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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