class Solution { public String minWindow(String s, String t) { // 创建要覆盖的字符串数组,容量为ASCII值的数量 int[] tArr = new int[256]; int tLen = t.length(); int sLen = s.length(); for(int i = 0;i < tLen;i++){ // 将t字符串出现的位置置为1 tArr[t.charAt(i)]++; } // 定义t字符串覆盖的情况 int count = t.length(); // 定义结果区间的的左右指针 int left = -1,right = -1; // 定义滑动窗口的左右指针 int start = 0; // 定义被覆盖的数组 int[] sArr = new int[256]; // 窗口默认大小 int len = Integer.MAX_VALUE; // 遍历s字符串 for(int end = 0;end < sLen;end++){ char c = s.charAt(end); // 更新当前字符所在位置的频率+1 sArr[c]++; // 若当前字符的频率小于等于要当前匹配的字符频率,说明匹配到了待匹配的字符 if(sArr[c] <= tArr[c]) // 可覆盖的字符-1 count--; // 当窗口大小超出范围或还有可覆盖的字符,跳出循环 // 窗口向前移动 while(start <= end && count == 0){ char h = s.charAt(start); sArr[h]--; if(sArr[h] < tArr[h]){ count++; } // 若t字符串中还有没出现的字符,更新当前窗口位置 if(count > 0){ // 更新当前窗口的位置 if(len > end - start + 1){ left = start; right = end; len = right - left + 1; } } // t字符串中还有没覆盖的字符,头指针前移 start++; } } // 若结果区间的左指针位置没变,说明字符串中没有符合的子串 if(left == -1) return ""; return s.substring(left,right + 1); } }
Ronan0