Minimum Window Substring, 包含子串的最小窗口，双指针

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

问题描述：给定字符串S，子串T，求S中包含T的最小窗口

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".

算法分析：对于滑动窗口的题目，一般都是设置左右指针。这道题，首先用map1统计T中每个字符数，然后遍历S字符串，用map2统计T中字符在S中的个数，用count记录相同字符数，如果count==t.length说明当前窗口包含T，然后通过map2对比map1，来滑动窗口。

public class MinWindowSubstring
{
public String minWindow(String s, String t) {
if(t.length()>s.length())
return "";
String result = ""; //统计t中每个字符的个数
HashMap<Character, Integer> target = new HashMap<Character, Integer>();
for(int i=0; i<t.length(); i++)
{
char c = t.charAt(i);
if(target.containsKey(c))
{
target.put(c,target.get(c)+1);
}
else
{
target.put(c,1);
}
} //map统计t中字符在s中的个数
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int left = 0;//窗口左指针
int minLen = s.length()+1;//最小窗口 int count = 0; // 统计s中包含t中元素数 for(int i=0; i<s.length(); i++)
{
char c = s.charAt(i); if(target.containsKey(c))
{
if(map.containsKey(c))
{
if(map.get(c)<target.get(c))
{
count++;
}
map.put(c,map.get(c)+1);
}
else
{
map.put(c,1);
count++;
}
}//target.containsKey(c) if(count == t.length())//当前窗口包含所有t中元素
{
char sc = s.charAt(left);
//从左边开始滑动窗口
while (!map.containsKey(sc) || map.get(sc) > target.get(sc))
{
if (map.containsKey(sc) && map.get(sc) > target.get(sc))
{
map.put(sc, map.get(sc) - 1);
} left++; sc = s.charAt(left);
}
//计算最小窗口
if (i - left + 1 < minLen)
{
result = s.substring(left, i + 1);
minLen = i - left + 1;
}
}//count == t.length }//for return result;
}
}