1罗洗、題目
image.png
2碌宴、分析
使用滑動(dòng)窗口的算法框架页慷。這道題還要注意下java處理字符串的常見的方法捏鱼。
/* 滑動(dòng)窗口算法框架 */
void slidingWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// c 是將移入窗口的字符
char c = s[right];
// 右移窗口
right++;
// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
...
/*** debug 輸出的位置 ***/
printf("window: [%d, %d)\n", left, right);
/********************/
// 判斷左側(cè)窗口是否要收縮
while (window needs shrink) {
// d 是將移出窗口的字符
char d = s[left];
// 左移窗口
left++;
// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
...
}
}
}
3执庐、代碼
class Solution {
public String minWindow(String s, String t) {
HashMap<Character, Integer> need = new HashMap<>();
HashMap<Character, Integer> window = new HashMap<>();
int isValible = 0;
int left = 0, rigth = 0;
int start = 0, len = Integer.MAX_VALUE;
for(int i = 0; i < t.length(); i++){
need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
}
while(rigth < s.length()){
char c = s.charAt(rigth);
rigth++;
if(need.containsKey(c)){
window.put(c, window.getOrDefault(c, 0) + 1);
//注意用equals，不要用 ==
if(window.get(c).equals(need.get(c))){
isValible++;
}
}
while(isValible == need.size()){
if(rigth - left < len){
start = left;
len = rigth - left;
}
char d = s.charAt(left);
left++;
if(need.containsKey(d)){
//主要要用equals
if(window.get(d).equals(need.get(d))){
isValible--;
}
window.put(d, window.getOrDefault(d, 0) - 1);
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}
}
