给定一个字符串source和一个目标字符串target，在字符串source中找到包括所有目标字符串字母的子串。

 注意事项

如果在source中没有这样的子串，返回""，如果有多个这样的子串，返回起始位置最小的子串。

说明

在答案的子串中的字母在目标字符串中是否需要具有相同的顺序？

——不需要。

样例

给出source = "ADOBECODEBANC"，target = "ABC" 满足要求的解  "BANC"

1：暴力方法

import java.util.HashMap; import java.util.Map; import java.util.Scanner; /** * 给定一个字符串source和一个目标字符串target，在字符串source中找到包括所有目标字符串字母的子串。 注意事项 如果在source中没有这样的子串，返回""，如果有多个这样的子串，返回起始位置最小的子串。 您在真实的面试中是否遇到过这个题？ Yes 说明 在答案的子串中的字母在目标字符串中是否需要具有相同的顺序？ ——不需要。 样例 给出source = "ADOBECODEBANC"，target = "ABC" 满足要求的解 "BANC" * * @author Dell * */ public class Test32 { public static String minWindow(String source,String target) { String result=""; for(int i=0;i<source.length();i++) { for(int j=i;j<source.length();j++) { String temp=source.substring(i, j+1); if(temp.length()<target.length()) continue; int k; boolean[] visited=new boolean[temp.length()]; for(k=0;k<target.length();k++) { boolean flag=false; for(int m=0;m<temp.length();m++) { if(target.charAt(k)==temp.charAt(m)&&visited[m]==false) { visited[m]=true; flag=true; break; } else continue; } if(flag==false) break; } if(k>=target.length()) { if(result==""||result.length()>temp.length()) { result=temp; } } } } return result; } public static void main(String[] args) { Scanner sc=new Scanner(System.in); String source=sc.nextLine(); String target=sc.nextLine(); System.out.println(minWindow(source,target)); } } 2：

给定一个字符串S和T，在S中找到一个最小的子串包含T中的所有字符，时间复杂度为O(n)。 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).

举例, S = "ADOBECODEBANC" T = "ABC" 最小子串是"BANC".

时间复杂度是O(n)

其中n是字符串S的长度，因为每个字符在维护窗口的过程中不会被访问多于两次。

空间复杂度则是O(1)

也就是代码中T的长度。

数据结构选择

记录字母出现次数的数据结构有采用哈希Map的也有采用数组的，这里介绍一下数组的用法，因为它用了比较取巧的方式。 大小写字母的ASCII码不大于128，这样array['A']=3指A出现3次，array['B']=1指B出现了一次，以此类推，不能用常规意义上的定义array[0]=3表示A出现3次，这样就多了一层映射！故而数组的长度设置为128即可存放所有的字母。明白了么？

算法思想：

首先预处理T，用一个128长 (示例代码用了256) 的整数数组srcHash存储里面每个目标字符出现的个数然后处理原串S，也用一个128长的整数数组destHash记录原串字符出现的个数。给定两个指针start和end，作为最小窗口的左右边界。具体实现看下代码一目了然。 public class Solution { public String minWindow(String S, String T) { int[] srcHash = new int[255]; // 记录目标字符串每个字母出现次数 for(int i = 0; i < T.length(); i++){ srcHash[T.charAt(i)]++; } int start = 0,i= 0; // 用于记录窗口内每个字母出现次数 int[] destHash = new int[255]; int found = 0; int begin = -1, end = S.length(), minLength = S.length(); for(start = i = 0; i < S.length(); i++){ // 每来一个字符给它的出现次数加1 destHash[S.charAt(i)]++; // 如果加1后这个字符的数量不超过目标串中该字符的数量，则找到了一个匹配字符 if(destHash[S.charAt(i)] <= srcHash[S.charAt(i)]) found++; // 如果找到的匹配字符数等于目标串长度，说明找到了一个符合要求的子串 if(found == T.length()){ // 将开头没用的都跳过，没用是指该字符出现次数超过了目标串中出现的次数，并把它们出现次数都减1 while(start < i && destHash[S.charAt(start)] > srcHash[S.charAt(start)]){ destHash[S.charAt(start)]--; start++; } // 这时候start指向该子串开头的字母，判断该子串长度 if(i - start < minLength){ minLength = i - start; begin = start; end = i; } // 把开头的这个匹配字符跳过，并将匹配字符数减1 destHash[S.charAt(start)]--; found--; // 子串起始位置加1，我们开始看下一个子串了 start++; } } // 如果begin没有修改过，返回空 return begin == -1 ? "" : S.substring(begin,end + 1); } }