代码1
Runtime: 3 ms, faster than 97.65% of Java online submissions for Minimum Window Substring.
class Solution {
public String minWindow(String s, String t) {
int[] source = new int[256];
int[] target = new int[256];
char[] s_char = s.toCharArray();
char[] t_char = t.toCharArray();
for (int i = 0; i < t_char.length; i++) {
target[t_char[i]]++;
}
String ans = "";
int length = s_char.length;
int found = 0;
for (int i = 0, j = 0; j < s_char.length; j++) {
source[s_char[j]]++;
if (source[s_char[j]] <= target[s_char[j]]) found++;
if (found == t_char.length) {
while (i < s_char.length
&& source[s_char[i]] > target[s_char[i]])
//排除开头多余的字符
source[s_char[i++]]--;
//如果长度有变小就保存
if (j - i + 1 <= length) {
ans = s.substring(i, j + 1);
length = j - i + 1;
}
//把第一个有用的字符排除看看之后有没有更小的
source[s_char[i++]]--;
found--;
}
}
return ans;
}
}
