题目描述
解题思路
用i,j表示滑动窗口的左边界和右边界，通过改变i,j来扩展和收缩滑动窗口，可以想象成一个窗口在字符串上游走，当这个窗口包含的元素满足条件，即包含字符串T的所有元素，记录下这个滑动窗口的长度j-i+1，这些长度中的最小值就是要求的结果。
解题代码
public String minWindow(String s, String t) {
if (s == null || s.length() == 0 || t == null || t.length() == 0) {
return "";
}
/**
* 总共128个字符
*/
int[] needs = new int[128];
int tsize = t.length();
for (int i = 0; i < tsize; i++) {
needs[t.charAt(i)]++;
}
int left = 0, right = 0;
/**
* 有效字符串的起始位置
*/
int start = 0;
/**
* 有效字符串的长度
*/
int size = Integer.MAX_VALUE;
int needSize = t.length();
while (right < s.length()) {
if (needs[s.charAt(right)] > 0) {
needSize--;
}
/**
* 不是需要的字符也纳入窗口中，并且赋值小于0
*/
needs[s.charAt(right)]--;
if (needSize == 0) {
/**
* 找到满足目标字符串中的第一个元素
*/
while (left < right && needs[s.charAt(left)] < 0) {
//释放左边无用的字符
needs[s.charAt(left)]++;
left++;//指针右移
}
int tempSize = right - left + 1;
if (tempSize < size) {
start = left;
size = tempSize;
}
needs[s.charAt(left)]++;
left++;
needSize++;
}
right++;
}
return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size);
}
解法2
public String minWindow(String s, String t) {
if (s == null || s.length() == 0 || t == null || t.length() == 0) {
return "";
}
int rigtMin = findRight(s, t);
int leftMax = findLeft(s,t);
return s.substring(leftMax,rigtMin);
}
private int findLeft(String s, String t) {
int left = 0;
while (true) {
String temp = s.substring(left, s.length());
if (temp.contains(t)) {
left++;
} else {
left--;
return left;
}
}
}
private int findRight(String s, String t) {
int right = s.length();
while (true) {
String temp = s.substring(0, right);
if (temp.contains(t)) {
right--;
} else {
right++;
return right;
}
}
}
}
