给你一个字符串 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 由英文字母组成
class Solution {public String minWindow(String s, String t) {/**思路1：暴力法。（1）对s进行遍历，同时对t进行遍历做比对记录第一个匹配到的位置，再次从当前位置进行匹配（2）找到第二个匹配的元素（要把第一个匹配到的元素remove）（3）继续循环上述操作，当找到第一个匹配的字符串的时候，记录长度，并用一个字符串来存储（4）如果下次循环找到的字符串小于当前记录的字符串，就替换掉，否则就继续循环思路2：滑动窗口法（1）定义两个指针（一左一右）（2）左指针不动，移动右指针，匹配到一个字符串（3）当匹配到一个最小的字符串的时候，把左边界向右移动具体解题步骤：（1）关键字：ASCII码字典表int[128]，左右边界l,r，滑动窗口的长度size，窗口中包含的字符串的数量count，下一次窗口的起始位置start（2）先对字符串t进行遍历（t包含的字符都在字典里面），设置一个ASCII码字典表数组，数组的值默认为0，找到了t中包含的字符，就对数组做-1操作（1代表没有找到，0代表已经有一个，负数代表有多余）（3）初始化几个变量：l,r滑动窗口左右指针，size滑动窗口大小，count找到的字符串个数，start，下一次的起始位置（4）第一层while循环，遍历s字符串，只要r右边界小于s的长度，就继续遍历，每遍历一次，右边界要向右移动（5）取出s中右边界位置的字符，并从ASCII码字典表中找到这个字符对应的值（默认为1），count做自减计算，代表当前滑动窗口包含这个字符（如果多次，就会成为负数，负数代表有重复），遍历到的这个字符在t中包含（6）无论遍历到的字符是否包含在t中，都对need[c]做自减，利用正负值区分多余还是有用（7）判断count==0，如果等于，说明已经找到了一个包含所有t中字符的子串（8）如果找到了，那么意味着需要移动滑动窗口的左边界（右边界在外层循环已经在移动）（9）while循环，当左边界的位置小于右边界，并且左边界所在的位置的字符，在need[]数组中的数值小于0（每次遍历的字符都要对need[c]做自增的原因，如果小于0，说明是个多余元素，要么就是多次重复出现，扣减到0了，这个时候还是要继续往后移动左指针，因为要找最小的窗口），则l++，右移一位，并且把need[]数组l字符对应的位置++（方便下一次滑动窗口）（10）跳出循环后，判读r-l+1是否小于size（即上次找到的窗口长度），如果小于，需要更新size，同时更新start为左边界l的位置（11）更新l位置元素的need值，因为start在这里开始的，这个元素也要考虑进去，否则，第一步count--的时候，会出错（12）因为start已经是一个字符了，所以，更新一下count++数量，更新一下滑动窗口的左边界，l++*///首先创建的是need数组表示每个字符在t中需要的数量，用ASCII码来保存//加入need[76] = 2，表明ASCII码为76的这个字符在目标字符串t中需要两个，如果是负数表明当前字符串在窗口中是多余的，需要过滤掉int[] need = new int[128];//按照字符串t的内容向need中添加元素---ASCII码字典表for (int i = 0; i < t.length(); i++) {need[t.charAt(i)]++;}/*l: 滑动窗口左边界r: 滑动窗口右边界size: 窗口的长度count: 当次遍历中还需要几个字符才能够满足包含t中所有字符的条件，最大也就是t的长度start: 如果有效更新滑动窗口，记录这个窗口的起始位置，方便后续找子串用*/int l = 0, r = 0, size = Integer.MAX_VALUE, count = t.length(), start = 0;//循环条件右边界不超过s的长度while (r < s.length()) {char c = s.charAt(r);//表示t中包含当前遍历到的这个c字符，更新目前所需要的count数大小，应该减少一个if (need[c] > 0) {count--;}//无论这个字符是否包含在t中，need[]数组中对应那个字符的计数都减少1，利用正负区分这个字符是多余的还是有用的need[c]--;//count==0说明当前的窗口已经满足了包含t所需所有字符的条件，所以需要做移动左边界的操作，滑动窗口if (count == 0) {//如果左边界这个字符对应的值在need[]数组中小于0，说明他是一个多余元素，不包含在t内while (l < r && need[s.charAt(l)] < 0) {//在need[]数组中维护更新这个值，增加1need[s.charAt(l)]++;//左边界向右移，过滤掉这个元素l++;}//如果当前的这个窗口值比之前维护的窗口值更小，需要进行更新if (r - l + 1 < size) {//更新窗口值size = r - l + 1;//更新窗口起始位置，方便之后找到这个位置返回结果start = l;}//先将l位置的字符计数重新加1need[s.charAt(l)]++;//重新维护左边界值和当前所需字符的值countl++;count++;}//右移边界，开始下一次循环r++;}return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size);}}
若有收获，就点个赞吧
0 人点赞
