视频教学网站开发,网络用户提要求找人帮忙做的网站,网络营销对传统营销有哪些冲击,给你一个网站你如何做优化题目链接#xff1a;力扣 解题思路#xff1a;滑动窗口
因为只需要最小子串中包含t中的所有字符即可#xff0c;顺序不重要#xff0c;所以可以先统计一下 t 中每个字符出现的次数#xff0c;使用map进行统计#xff1a; key表示t中的字符#xff0c;value表示字符的个…题目链接力扣 解题思路滑动窗口
因为只需要最小子串中包含t中的所有字符即可顺序不重要所以可以先统计一下 t 中每个字符出现的次数使用map进行统计 key表示t中的字符value表示字符的个数值为正数时表示滑动窗口中需要value个字符值为负数时表示滑动窗口中多余了 -value个字符初始值 result 保存最小子串num 0窗口中包含的 t 中的有效字符个数如果t中字符a有两个滑动窗口中已经有两个a了这个时候右遇到一个anum并不加1因为这个a是无效的left 0滑动窗口的左边界right 0滑动窗口的右边界不断左移滑动窗口的右边界当numt.length找到了一个字串包含所有t中的字符但是这个时候滑动窗口的左边界可能会有一些无效的字符或者多余的字符 比如 BABC子串包含t BC但是前面的BA是无效的可以删去最小子串为BC具体移动过程如下如果right s.length则一直往右移动 如果 map.containsKey(s.charAt(right))当前字符是 t 中的字符 如果map.get(s.charAt(right)) 0说明滑动窗口中包含当前字符的个数小于t中的字符个数令 nummap.put(s.charAt(right)map.get(s.charAt(right))-1)令当前字符个数 -1方便后面缩小滑动窗口的左边界如果 num t.length说明滑动窗口中已经包含了所有t中的字符但这个时候左边界可能有一些不在t中的字符或者多余的字符。需要循环缩小左边界 如果 左边界的字符不在 t中或者 map.get(s.charAt(left)) 0即字符有多余这两种情况下都需要收缩 如果在t中并且map中的值小于0说明左边界这个字符是多余的令map中的值1left如果result.equal()或者 right - left 1 result.length()更短的子串 令result s.substring(left,right1)
AC代码
class Solution {public static String minWindow(String s, String t) {char[] sStr s.toCharArray();char[] tStr t.toCharArray();MapCharacter, Integer map new HashMap();for (char c : tStr) {map.put(c, map.getOrDefault(c, 0) 1);}int left 0;String result ;//记录滑动窗口中包含多少个t中的字符int num 0;for (int right 0; right sStr.length; right) {if (map.containsKey(sStr[right])) {if (map.get(sStr[right]) 0) {num;}map.put(sStr[right], map.get(sStr[right]) - 1);}if (num tStr.length) {//缩小窗口右边界while (!map.containsKey(sStr[left]) || map.get(sStr[left]) 0) {if (map.containsKey(sStr[left])) {map.put(sStr[left], map.get(sStr[left]) 1);}left;}if (result.equals() || right - left 1 result.length()) {result s.substring(left, right 1);}}}return result;}
} 使用集合进行统计滑动窗口中需要的字符个数或者多余的字符个数效率较低可以使用hash表进行优化思路类似只不过将map换成hash表
AC代码
class Solution {public static String minWindow(String s, String t) {char[] sStr s.toCharArray();char[] tStr t.toCharArray();int[] hash new int[128];for (char c : tStr) {hash[c];}int left 0;String result ;//记录滑动窗口中包含多少个t中的字符int num 0;for (int right 0; right sStr.length; right) {hash[sStr[right]]--;if (hash[sStr[right]] 0) {num;}while (num tStr.length hash[sStr[left]] 0) {hash[sStr[left]];}if (num tStr.length (result.equals() || right - left 1 result.length())) {result s.substring(left, right 1);}}return result;}
}
