Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,S="ADOBECODEBANC"T="ABC"
Minimum window is"BANC".
Note:If there is no such window in S that covers all characters in T, return the emtpy string"".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
思路：此题就是求解最小包含T的子串，最优解法是O(n)时间复杂度。思想是用两个128的int数组，分别保存s和t的字符的个数。
start,end首尾双指针，对s进行遍历，end++时，将s.charAt(end)对应的int数组值+1，start++时，将s.charAt(start)对应的int数组值-1.
当找到满足符合要求的end时，与最小的长度比较，比最小的长度还小，则交换数值，否则，start跳转合适的位置，同时s.charAt(start)对应的数组-1.
具体代码如下：
public class Solution {public String minWindow(String s, String t) {char[] cS = s.toCharArray();//转换成数组，以后操作更方便快捷char[] cT = t.toCharArray();if(cS.length ==0 || cT.length==0){return "";//如果有为空，返回空}//定义匹配的字符串最小匹配长度int len = Integer.MAX_VALUE;int[] sA = new int[128];//存储s字符串中字符的个数int[] tA = new int[128];//存储t字符个数//将比较的字符串记录在数组中for(int i = 0; i < cT.length; i++){tA[t.charAt(i)]++;}int start = 0;//起始int end = 0;//结束int s0 = 0;//保存最小长度的起始值int e0 = 0;//保存最小长度的结束值int it = 0;//t字符串的起始boolean isEndAdd = true;//end指针时候变动//遍历while(end < cS.length){//System.out.println("start:" + start);if(isEndAdd)//只有end+1才添加sA[cS[end]]++;if(end – start >= cT.length-1){//只有字符长度大于t的长度才比较while(it < cT.length){//t字符的当前位置if(tA[cT[it]] <= sA[cT[it]]){//如果一个字符个数相等了，比较下一个字符it++;}else{break;//如果不相等，直接结束循环}}if(it == cT.length){//符合要求if(len > end – start + 1){//如果值小于当前s0 = start;//更新起始值e0 = end+1;len = e0 – s0;//更新长度}else{//如果len长度比当前长度小，，则当前起始直接到len宽度的起始，也即strat = end – len;for(;start <= end – len;start++){sA[cS[start]]–;//同时将sA数组的字符数-1}}sA[cS[start]]–;start++;//要比当前长度小1isEndAdd = false;it = 0;//后面重新匹配}else{isEndAdd = true;end++;}}else{isEndAdd = true;end++;}}return s.substring(s0,e0);}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
你曾经说，你曾经说。走在爱的旅途，我们的脚步多么轻松……
