leetCode第76题最小覆盖字串（滑动窗口算法）

本文主要是介绍leetCode第76题最小覆盖字串（滑动窗口算法），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

大家好，我是魔笑，下面是我分享的滑动窗口算法题，这道题我真是弄了好久，写完，拿到leetCode验证，然后一遍一遍的纠正。真的不容易，最终提交成功，如果对你有帮助，请给个赞啊亲。我们一起加油

题目：

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

滑动窗口算法：

* 在滑动窗口类型的问题中都会有两个指针，一个用于「延伸」现有窗口的 r 指针，和一个用于「收缩」窗口的 l 指针。在任意时刻，只有一个指针运动，而另一个保持静止。我们在 s 上滑动窗口，通过移动 r 指针不断扩张窗口。当窗口包含 t 全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口。

下面是我的解题思路：

*  集合tMap:将所有字符串t中所有的字符放入tMap集合；
*  集合cMap:将左指针和右指针之间的所有属于tMap集合字符放入cMap中，和tMap做对比
*  步骤一，左指针不动，右指针向右移动（窗口在增大），并且将属于s字符串的字符都加入cMap集合中，直到cMap中的字符不少于tMap，并且cMap中每个字符的数量都大于等于tMap数量（满足结果，得到结果），然后步骤二
*  步骤二，右指针不动，左指针向右移动（窗口在缩小），并且从cMap集合中删除右指针所在的字符,直到不满足cMap中每个字符的数量都大于等于tMap数量，然后再重复步骤一。

例如：

*例如：s:"abbc",t:"bc"
* tMap:[a:1,b:1]
* 步骤一：左指针下标是0，右指针下标是-1。
         左指针不动，右指针右移。
         右指针移动到下标是3并且将所有属于tMap元素加入cMap[b:2,c:1]，满足条件，
          那么最小字串是“abbc”。

* 步骤二：右指针不动，左指针右移。
          ‘a’不属于tMap（指针增加），左指针下标为1
          当指针是下标1时，‘b’属于cMap，删除cMap中是b的字符（数量减一）指针增加，这时指针是2，
          这时cMap[b:1,c:1]满足条件，那么最小字符串是："bc"

代码：

  public static String minWindow2(String s, String t) {
        int sLength = s.length();
        int tLength = t.length();
        //如果t字符串大于s字符串直接返回
        if (tLength < tLength) {
            return "";
        }
        Map<Character, Integer> tMap = new HashMap();
        Map<Character, Integer> cMap = new HashMap();
        //将t字符串中所有字符放到tMap中，key是字符，value是这个字符的数量
        for (int i = 0; i < tLength; i++) {
            tMap.put(t.charAt(i), (Integer) tMap.getOrDefault(t.charAt(i), 0) + 1);
        }
        int right = -1;
        int left = 0;
        //存放满足条件的最小的左指针和右指针所在的下标
        int leftResult = 1;
        int rightResult = Integer.MAX_VALUE;
        //遍历s字符串
        for (left = 0; left < sLength; left++) {
            //去除不属于t的字符
            if (!tMap.containsKey(s.charAt(left))) {
                continue;
            }
            //"ad ob ec od eb an cb bc aa"
            //右指针不动，左指针向右移动（窗口在缩小）。
            // 并且从原集合中删除右指针所在的字符，直到不满足cMap中每个字符的数量都大于等于tMap数量.
            while (isEquals(tMap, cMap) && left < right) {
                if (right - left + 1 < rightResult - leftResult + 1) {
                    leftResult = left;
                    rightResult = right;
                }
                if (tMap.containsKey(s.charAt(left))) {
                    cMap.put(s.charAt(left), cMap.getOrDefault(s.charAt(left), 0) - 1);
                }
                left++;
            }
            //左指针不动，右指针向右移动（窗口在增大），并且将属于s字符串的字符都加入对比集合中.
            // 直到cMap中的字符不少于tMap，并且cMap中每个字符的数量都大于等于tMap数量.
            while (right + 1 < sLength) {
                if (!tMap.containsKey(s.charAt(right + 1))) {
                    right++;
                    continue;
                }
                //将属于s字符串的字符都加入cMap集合中
                cMap.put(s.charAt(right + 1), (Integer) cMap.getOrDefault(s.charAt(right + 1), 0) + 1);
                if (isEquals(tMap, cMap)) {
                    if (right + 1 - left + 1 < rightResult - leftResult + 1) {
                        leftResult = left;
                        rightResult = right + 1;
                    }
                    right++;
                    break;
                }
                right++;

            }
            //删除左指针所在下标中cMap包含的字符
            if (tMap.containsKey(s.charAt(left))) {
                cMap.put(s.charAt(left), cMap.getOrDefault(s.charAt(left), 0) - 1);
            }

        }
        if (rightResult - leftResult + 1 == Integer.MAX_VALUE) {
            return "";
        }
        return s.substring(leftResult, rightResult + 1);
    }
    /**
        判断cMap中每个字符的数量是否都大于等于tMap数量
    */
    public static boolean isEquals(Map tMap, Map cMap) {
        if (tMap.size() != cMap.size()) {
            return false;
        }
        Iterator iterator = cMap.keySet().iterator();
        while (iterator.hasNext()) {
            Character character = (Character) iterator.next();
            if ((Integer) tMap.get(character) > (Integer) cMap.get(character)) {
                return false;
            }
        }
        return true;
    }

优化后的代码二：

    public static String minWindow3(String s, String t) {
        int sLength = s.length();
        int tLength = t.length();
        //如果t字符串大于s字符串直接返回
        if (tLength < tLength) {
            return "";
        }
        Map<Character, Integer> tMap = new HashMap();
        Map<Character, Integer> cMap = new HashMap();
        //将t字符串中所有字符放到tMap中，key是字符，value是这个字符的数量
        for (int i = 0; i < tLength; i++) {
            tMap.put(t.charAt(i), (Integer) tMap.getOrDefault(t.charAt(i), 0) + 1);
        }
        int right = -1;
        int left = 0;
        //存放满足条件的最小的左指针和右指针所在的下标
        int leftResult = 1;
        int rightResult = Integer.MAX_VALUE;
        while (right + 1 < sLength) {
            if (!tMap.containsKey(s.charAt(right + 1))) {
                right++;
                continue;
            }
            //将属于s字符串的字符都加入cMap集合中
            cMap.put(s.charAt(right + 1), (Integer) cMap.getOrDefault(s.charAt(right + 1), 0) + 1);
            while (isEquals(tMap, cMap) && left <= right+1) {
                if (right+1 - left + 1 < rightResult - leftResult + 1) {
                    leftResult = left;
                    rightResult = right+1;
                }
                //删除左指针所在下标中cMap包含的字符
                if (tMap.containsKey(s.charAt(left))) {
                    cMap.put(s.charAt(left), cMap.getOrDefault(s.charAt(left), 0) - 1);
                }
                left++;
            }
            right++;

        }

        if (rightResult - leftResult + 1 == Integer.MAX_VALUE) {
            return "";
        }
        return s.substring(leftResult, rightResult + 1);
    }
    /**
     * cMap中每个字符的数量都大于等于tMap数量
     */
    public static boolean isEquals(Map tMap, Map cMap) {
        if (tMap.size() != cMap.size()) {
            return false;
        }
        Iterator iterator = cMap.keySet().iterator();
        while (iterator.hasNext()) {
            Character character = (Character) iterator.next();
            if ((Integer) tMap.get(character) > (Integer) cMap.get(character)) {
                return false;
            }
        }
        return true;
    }

如果有什么问题，请多多指教。如果对你有帮助请给一个素质三连，谢谢。

这篇关于leetCode第76题最小覆盖字串（滑动窗口算法）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！