76.最小覆盖子窜

本文主要是介绍76.最小覆盖子窜，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

76.最小覆盖子窜

解题思路：双指针滑动窗口

package leadcode;import java.util.HashMap;
import java.util.Map;/*** @author : icehill* @description : 最小覆盖子窜* 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果s中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。* 注意：如果s中存在这样的子串，我们保证它是唯一的答案。* 示例 1：* 输入：s = "ADOBECODEBANC", t = "ABC"* 输出："BANC"* 示例 2：* 输入：s = "a", t = "a"* 输出："a"* 提示：* 1 <= s.length, t.length <= 105* s 和 t 由英文字母组成* 进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？* <p>* 来源：力扣（LeetCode）* 链接：https://leetcode-cn.com/problems/minimum-window-substring* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。* 题目分析：* 需要找到s的子窜，并且子窜必须包含t中所有的字符，且字符出现的频率必须大于t* 例如s=abcb t=aab，s中无法覆盖t* 1.暴力解法（不考虑）* 枚举s所有长度大于t的子窜，判断子窜是否覆盖t* 时间复杂度：O(n^3) 空间复杂度O(n) (n为s的长度，求s的子窜，n^2，对于子窜，再判断频数跟t比较n，所以总的n^3)* 由于子窜的判断中做了很多重复的工作，或者没必要的工作，所以我们不考虑这种解法* 2.我们使用双指针的滑动窗口解题* 例如：s=aadobecodebanc t=abc* a.移动右指针找到第一个覆盖t* s=[aadobec]odebanc* b.移动左指针，直到不满足覆盖t* s=a[adobec]odebanc* c.右指针向右移动并探测，如果找到一个属于t的字符，重复b尝试移动右指针，记录当前窗口是否是最小值* s=a[adobecodeb]anc* s=aadobe[codeba]nc* s=aadobecode[banc]* d.返回最小子窜* @date : 2021-05-18*/
public class Solution76 {public static void main(String[] args) {Solution76 solution76 = new Solution76();
//        System.out.println(solution76.minWindow("ADOBECODEBANC", "ABC"));System.out.println(solution76.minWindow("bba", "ab"));}public String minWindow(String s, String t) {Map<Character, Integer> tMap = new HashMap<>();Map<Character, Integer> targetMap = new HashMap<>();//把t转换成哈希表，并统计数量for (int i = 0; i < t.length(); i++) {if (!tMap.containsKey(t.charAt(i))) {tMap.put(t.charAt(i), 1);targetMap.put(t.charAt(i), 0);} else {tMap.put(t.charAt(i), 1 + tMap.get(t.charAt(i)));}}int count = 0;int start = -1;int end = -1;//移动右指针，直到找到第一个符合的子窜for (int j = 0; j < s.length(); j++) {if (tMap.containsKey(s.charAt(j))) {if (start == -1) {start = j;}targetMap.put(s.charAt(j), 1 + targetMap.get(s.charAt(j)));if (targetMap.get(s.charAt(j)) <= tMap.get(s.charAt(j))) {count++;}}if (count >= t.length()) {end = j;break;}}if (count != t.length()) {return "";}//移动左指针，直到刚好满足覆盖子窜，就是当前右指针所在位置对应的最小子窜while (start < end + 1) {if (targetMap.get(s.charAt(start)) == null) {start++;continue;}if (targetMap.get(s.charAt(start)) > tMap.get(s.charAt(start))) {targetMap.put(s.charAt(start), targetMap.get(s.charAt(start)) - 1);start++;} else {break;}}int slow = start;//移动右指针，扩大滑动窗口for (int fast = end + 1; fast < s.length(); fast++) {if (tMap.containsKey(s.charAt(fast))) {targetMap.put(s.charAt(fast), 1 + targetMap.get(s.charAt(fast)));//移动左指针，缩小滑动窗口while (slow < fast) {if (targetMap.get(s.charAt(slow)) == null) {slow++;continue;}if (targetMap.get(s.charAt(slow)) > tMap.get(s.charAt(slow))) {targetMap.put(s.charAt(slow), targetMap.get(s.charAt(slow)) - 1);slow++;} else {break;}}if (fast - slow < end - start) {start = slow;end = fast;}}}return s.substring(start, end + 1);}
}

这篇关于76.最小覆盖子窜的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---