剑指 Offer II 017. 含有所有字符的最短字符串 滑动窗口

剑指 Offer II 017. 含有所有字符的最短字符串 滑动窗口

做题结果

成功，就是个简单的滑动窗口

方法：滑动窗口

1.预处理计算出 t 中每种字符的数目

2. 给定一个指针 i作为字符串结束标记点，逐步向右侧移动

3. 移动时，如果遇到的是目标t中存在的字符，则进行累加；如果数目未超过指定数目，说明匹配长度多了一个，长度计数加1

4. 缩短左侧长度，向又移动start,当缩短左侧不会影响匹配长度时，右移。当刚刚好现在的某字符数目和 t 的字符数目相等时，则说明影响到匹配长度了，匹配长度减1，循环结束

5. 所以此时以 i 结尾最短的长度，是 start 到 i 这一段，先不截取，只记录端点（因为截取过程比较耗时，所以留在返回时处理）

6. 继续移动，直到完成遍历

class Solution { public String minWindow(String s, String t) { int n = s.length(); int m = t.length(); int []cnts = new int[255]; for(int i =0; i < m; i++){ cnts[id(t.charAt(i))]++; } int len = 0; int []now = new int[255]; int start = 0; int as = 0; int ae = Integer.MAX_VALUE; for(int i = 0; i < n; i++){ int index = id(s.charAt(i)); if(cnts[index]>0){ now[index]++; if(now[index]<=cnts[index])++len; } while (len==m) { int id = id(s.charAt(start)); if(now[id]!=0){ if(now[id]==cnts[id])--len; --now[id]; } ++start; } if(len == m && i-start+1

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。