Minimum Window Substring, 包含子串的最小窗口，双指针
2024-09-23 23:21:56
问题描述：给定字符串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;
}
}
最新文章
- JS虚拟键盘
- IBatis学习
- 【转】mysql安装图解
- 《JavaScript权威指南》读书笔记（四）
- Windows 10 LNK File分析
- Android中不混淆类中函数
- Connecting Universities
- 加载window事件
- 用JS添加文本框案例代码
- HDU 1176 免费馅饼：dp
- MySQL高可用架构之MHA 原理与实践
- html5 contenteditable 实现table可编辑（网页版EXCEL）
- if-else语句
- 如何生成SSH key及查看SSH key
- 非常不错的地区三级联动，js简单易懂。封装起来了
- 关于CALayer 中的contents（图片） 拉伸
- python下的Box2d物理引擎的配置
- SpringData_CrudRepository接口
- #leetcode刷题之路21-合并两个有序链表
- ubuntu 安装linux 下vmVMware tools 步骤及问题解决