[C++知识库]【滑动窗口】最小覆盖子串

练题呀练题

【滑动窗口】
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”

链接：https://leetcode-cn.com/problems/minimum-window-substring

在这里插入代码片/**
 * 滑动窗口
 */
class Solution {
        public static String minWindow(String s, String t) {
            //类似于字典，使用一个一维数组need[]以ASCII码作为索引管理相应字符数目
            int[] need = new int[128];
            for (int i = 0; i < t.length(); i++)//将t中已有的元素在need中记录数量
                need[t.charAt(i)]++;

            int count = t.length();//定义一个整型变量用于记录窗口所需要的进入的t的元素数量
            int size = Integer.MAX_VALUE;//用于记录窗口的最小长度，记得更新
            int start = 0;//用于记录求得最短窗口的开始下标
            int l = 0,r = 0;//窗口左右边界

            while (r < s.length())//右边界不小于字符串s长
            {
                char c = s.charAt(r);//窗口右边界移动到的字符
                if (need[c] > 0)//表示t中相应元素还未全在窗口中
                    count--;//将该元素吞进窗口,还需要进窗口的元素数目减1
                need[c]--;//进窗口的字符元素数目在need中减1


                if (count == 0)//此时所需字符已经全部进入窗口
                {
                    //此时左边界不一定是所需要的字符
                    // 不要少了左边界需要小于右边界的条件,一开始我写的条件是(l < r && s.charAt(l) != t.charAt(0))
                    //但显然，就算是需要的t中的字符也可能在我们的窗口中多余,应该修改条件
                    while (l < r && need[s.charAt(l)] < 0){
                        need[s.charAt(l++)]++;//是多余字符时把其踢出窗口使对应need数组元素值加1并使左边界右移一位
                    }
                    //需要看看是否需要更新字典
                    if (r - l + 1 < size)
                    {
                        size = r - l + 1;
                    //更新目前最短窗口的下标
                        start = l;
                    }//一开始少写了大括号导致错误！！！
                    //使左边界继续向右移动，看是否能有更短的窗口,别忘了将对应need与count加1
                    need[s.charAt(l++)]++;
                    count++;
                }
                r++;//写while时先放在程序里，需要修改时修改
            }
            return size == Integer.MAX_VALUE ? "": s.substring(start,start+size);
        }
}