lc76 Minimum Window Substring
haspmap（也可以用数组[26]）和双指针
hashmap用来统计target字符串每种字符的个数，以此来检测source子串是否满足条件
双指针，
一个right用来遍历source字符串，也是计算满足条件子串长度时的右侧边界
一个left是左侧边界 每次碰到满足条件的子串，left一直更新，直到left所指元素为target不可或缺的一部分，即去掉left所指元素这个子串就不满足题意
1 class Solution { 2 public String minWindow(String s, String t) { 3 if(s == null || s.length() < t.length() || t == null) 4 return ""; 5 char[] ss = s.toCharArray(); 6 char[] tt = t.toCharArray(); 7 8 HashMap<Character, Integer> map = new HashMap<>(); 9 10 int left = 0; 11 int count = 0; 12 int minLen = ss.length + 1; 13 int minLeft = 0; 14 for(char i : tt){ 15 if(!map.containsKey(i)){ 16 map.put(i, 1); 17 }else{ 18 map.put(i, map.get(i) + 1); 19 } 20 } 21 22 for(int right = 0; right < ss.length; right++){ 23 if(map.containsKey(ss[right])){ 24 map.put(ss[right], map.get(ss[right]) - 1); 25 if(map.get(ss[right]) >= 0) 26 count++; 27 while(count == tt.length){ 28 if(right - left + 1 < minLen){ 29 minLeft = left; 30 minLen = right - left + 1; 31 } 32 if(map.containsKey(ss[left])){ 33 map.put(ss[left], map.get(ss[left]) + 1); 34 if(map.get(ss[left]) > 0) 35 count--; 36 } 37 left++; 38 } 39 } 40 } 41 if(minLen > ss.length) 42 return ""; 43 44 return s.substring(minLeft, minLeft + minLen); 45 } 46 }