Leetcode面试经典150题-76.最小覆盖子串

解法都在代码里，不懂就留言或者私信

理论上提交这个就是最优解

class Solution {
    public String minWindow(String s, String t) {
        if(s.length() < t.length()) {
            return "";
        }
        /**转成字符数组 */
        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();
        /**其他情况我们构建一个一个欠账表，这里可以用hashMap，也可以使用数组
        hashMap可能更直观一些，我们还有一个遍历count用来记录我们一共欠了多少*/
        Map<Character, Integer> countMap = new HashMap<>();
        int count = tArr.length;
        for(int i = 0; i < tArr.length ; i++) {
            countMap.put(tArr[i], countMap.getOrDefault(tArr[i], 0) + 1);
        }
        /**本题我们使用滑动窗口解题，left是左边界(包含)，right是右边界(不包含)
        窗口就是[left, right)，开始值都是0，代表还没有任何数据*/
        int left = 0, right = 0;
        /**遍历字符串s，进行还款 */
        int minWidth = Integer.MAX_VALUE;
        /**记录得到最小值时的开始和结束的下标 */
        int minStartIndex = 0;
        int minEndIndex = 0;
        while(right < sArr.length) {
            /**只要还是还完的状态就不断的缩小窗口，直到欠债，我们现在就尝试让窗口缩小（left右移），但是我们缩小之前需要记录一下当前的窗口大小 */
            while(count == 0) {
                minWidth = Math.min(minWidth, right - left);
                /**如果当前窗口长度就是整个的最小长度，那更新得到最小值时的开始和结束的下标为当前窗口的开始和结束 */
                if(minWidth == right - left) {
                    minStartIndex = left;
                    minEndIndex = right;
                }
                /**如果left位置这个字符是tArr里右的并且我们当前没有多还，那left退出之后我们实际欠的就多了一个
                如果这个字符不是tArr里真实存在的那就不管*/
                if(countMap.containsKey(sArr[left])) {
                    /**有效字符并且之前没有多还，count就增多了1个 */
                    if(countMap.get(sArr[left]) >= 0) {
                        count ++;
                    }
                    countMap.put(sArr[left], countMap.get(sArr[left]) + 1);
                }
                left ++;
            }
            /**走到这肯定是欠债状态，那就尝试right右扩增大窗口试试能不能还上*/
            if(countMap.containsKey(sArr[right])) {
                /**如果原来确实欠了这个位置的字符才会影响count */
                if(countMap.get(sArr[right]) > 0) {
                    count --;
                }
                countMap.put(sArr[right], countMap.get(sArr[right]) - 1);
            }
            right ++;
        }
        /**走出循环如果还是不欠债，试试能不能让窗口在不再次负债的情况下缩小*/
        while(count == 0) {
            minWidth = Math.min(minWidth, right - left);
            if(minWidth == right - left) {
                minStartIndex = left;
                minEndIndex = right;
            }
            /**如果left位置这个字符是tArr里右的并且我们当前没有多还，那left退出之后我们实际欠的就多了一个
            如果这个字符不是tArr里真实存在的那就不管*/
            if(countMap.containsKey(sArr[left])) {
                /**有效字符并且之前没有多还，count就增多了1个 */
                if(countMap.get(sArr[left]) >= 0) {
                    count ++;
                }
                countMap.put(sArr[left], countMap.get(sArr[left]) + 1);
            }
            left ++;
        }
        /**如果最后有答案的话返回得到最小值时的窗口*/
        return minWidth == Integer.MAX_VALUE? "" : s.substring(minStartIndex, minEndIndex);
    }
}